[CF855G]Harry Vs Voldemort

青旅半醒 2021-12-19 14:51 161阅读 0赞

# \[CF855G\]Harry Vs Voldemort #

## 题目大意： ##

一棵\\(n(n\\le10^5)\\)个结点的树，\\(q(q\\le10^5)\\)次操作，每次增加一条新边。每次操作后，你需要统计形如\\((u,v,w)\\)的三元组的数量，使得\\(u,v,w\\)都不相同，并存在两条分别\\(u\\)到\\(w\\)和\\(v\\)到\\(w\\)的路径，使得两条路径没有共同边。

## 思路： ##

每次加边相当于将两个顶点之间的所有边缩成了一个边双连通分量。

考虑三元组\\((u,v,w)\\)：

1.  \\(u,v,w\\)均在同一个边双中；
2.  \\(u,v\\)中有一个在与\\(w\\)相同的边双中；
3.  \\(u,v,w\\)均在不同的边双中。

对三种情况分别讨论即可。

对于情况2,3，只需维护边双大小\\(size\[u\]\\)；对于情况1，还需维护子树大小\\(tsize\[u\]\\)，和\\(u,v\\)分布在相同（或不同）子树中的方案数。

边双缩点可以用并查集实现。

时间复杂度\\(\\mathcal O(n\\alpha(n))\\)。

## 源代码： ##

#include<cstdio> #include<cctype> #include<vector> #include<numeric> inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x; } typedef long long int64; const int N=1e5+1; std::vector<int> e[N]; inline void add_edge(const int &u,const int &v) { e[u].push_back(v); e[v].push_back(u); } int64 ans,val[N],tmp[N]; int n,par[N],dep[N],size[N],tsize[N]; struct DisjointSet { int anc[N]; void reset(const int &n) { std::iota(&anc[1],&anc[n]+1,1); } int find(const int &x) { return x==anc[x]?x:anc[x]=find(anc[x]); } void merge(const int &x,const int &y) { anc[find(x)]=find(y); } bool same(const int &x,const int &y) { return find(x)==find(y); } }; DisjointSet djs; void dfs(const int &x,const int &par) { ::par[x]=par; dep[x]=dep[par]+1; size[x]=tsize[x]=1; for(int y:e[x]) { if(y==par) continue; dfs(y,x); tsize[x]+=tsize[y]; } } int64 calc(const int &x) { int64 ans=0; ans+=1ll*size[x]*(size[x]-1)*(size[x]-2);//XXX ans+=2ll*size[x]*(size[x]-1)*(n-size[x]);//XX-Y & Y-XX ans+=1ll*(n-size[x])*(n-size[x])*size[x]; for(int y:e[x]) {//Y-X-Z & Z-X-Y if(djs.same(x,y)) continue; const int z=djs.find(y); const int sz=y==par[x]?n-tsize[x]:tsize[z]; ans-=1ll*sz*sz*size[x]; tmp[x]+=1ll*sz*sz; } return val[x]=ans; } int64 calc2(const int &x) { int64 ans=0; ans+=1ll*size[x]*(size[x]-1)*(size[x]-2);//XXX ans+=2ll*size[x]*(size[x]-1)*(n-size[x]);//XX-Y & Y-XX ans+=1ll*(n-size[x])*(n-size[x])*size[x];//Y-X-Z & Z-X-Y ans-=tmp[x]*size[x]; return val[x]=ans; } void merge(int u,int v) { u=djs.find(u); v=djs.find(v); while(u!=v) { if(dep[u]<dep[v]) std::swap(u,v); const int w=djs.find(par[u]); tmp[w]-=1ll*tsize[u]*tsize[u]; tmp[w]+=tmp[u]-1ll*(n-tsize[u])*(n-tsize[u]); ans-=val[u]; size[w]+=size[u]; djs.merge(u,w); u=w; } ans-=val[u]; ans+=calc2(u); } int main() { n=getint(); for(register int i=1;i<n;i++) { add_edge(getint(),getint()); } djs.reset(n); dfs(1,0); for(register int x=1;x<=n;x++) { ans+=calc(x); } printf("%lld\n",ans); const int q=getint(); for(register int i=0;i<q;i++) { merge(getint(),getint()); printf("%lld\n",ans); } return 0; }

转载于:https://www.cnblogs.com/skylee03/p/10903969.html