BZOJ 3991 set维护dfs序

2019-11-06 07:29:54

字体：大中小

来源：转载

供稿：网友

思路： set按照dfn排序两点之间的距离可以O(logn)算出来加一个点-> now ans+=dis(PRe,now)+dis(now,next)-dis(pre-next); 删一个点同理最后加上dis(begin,end)即可

//By SiriusRen#include <set>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=200050;typedef long long ll;int first[N],next[N],v[N],w[N],tot,cnt,rev[N];int n,m,xx,yy,zz,dfn[N],deep[N],fa[N/2][20];ll ans,wei[N],temp;struct cmp{bool Operator()(int x,int y){return dfn[x]<dfn[y];}};set<int,cmp>s;set<int,cmp>::iterator it,itpre,itnext;void add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){ dfn[x]=++cnt; for(int i=first[x];~i;i=next[i]) if(v[i]!=fa[x][0]) deep[v[i]]=deep[x]+1,wei[v[i]]=wei[x]+w[i],fa[v[i]][0]=x,dfs(v[i]);}int lca(int x,int y){ if(deep[x]<deep[y])swap(x,y); for(int i=19;i>=0;i--)if(deep[x]-(1<<i)>=deep[y])x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0];}ll dis(int x,int y){return wei[x]+wei[y]-2*wei[lca(x,y)];}int main(){ memset(first,-1,sizeof(first)); scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ scanf("%d%d%d",&xx,&yy,&zz); add(xx,yy,zz),add(yy,xx,zz); } dfs(1),deep[1]=1; for(int j=1;j<=19;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; while(m--){ scanf("%d",&xx); rev[xx]^=1; if(rev[xx]){ s.insert(xx),it=s.lower_bound(xx); itnext=++it,--it; if(it!=s.begin())itpre=--it,++it,ans+=dis(*itpre,*it); if(itnext!=s.end())ans+=dis(*itnext,*it); if(it!=s.begin()&&itnext!=s.end())ans-=dis(*itpre,*itnext); } else{ it=s.lower_bound(xx); itnext=++it,--it; if(it!=s.begin())itpre=--it,++it,ans-=dis(*itpre,*it); if(itnext!=s.end())ans-=dis(*itnext,*it); if(it!=s.begin()&&itnext!=s.end())ans+=dis(*itpre,*itnext); s.erase(it); } it=s.end(); if(s.size()>1)temp=dis(*s.begin(),*(--it)); else temp=0; printf("%lld/n",ans+temp); }}

这里写图片描述