直接建边边数过多，不好处理。我们可以考虑建一些虚点，让 \(u_i\) 和 \(n+i\) 连边，\(v_i\) 和 \(n+i\) 连边。设这些新连的点为白点，与白点有连边的点在原图中一定相连，并且一定是一棵树。删除操作相当于把 \(u\) 的子白点连到他的父白点上，使用并查集维护即可。
这时再考虑如何算答案。把三元组 \((a,b,c)\) 变成 \((a,x,b,y,c)\) （\(x,y\) 就是白色点），再记 \(f_u\) 表示白点 \(u\) 的黑儿子个数，分情况讨论一下：
- 当 \(x=y\) 时，相当于在 \(x\) 的邻点中任选三个，\(x\) 的邻点有 \(f_x+1\) 个（因为要算上他的父亲）。故对答案的贡献为 \(\displaystyle\sum_{x \in white} (f_x+1)f_x(f_x-1)\)。
- 当 \(x \ne y\) 时，若 \(x,y\) 为 \(b\) 的儿子，那么相当于在 \(x,y\) 中选 \(a,c\)，贡献为 \(\displaystyle\sum_{x,y \in son_b,x \ne y} f_x f_y\)。变一下形，即 \((\sum f_x)^2 - \sum (f_x)^2\)。
- 当 \(x\) 为 \(b\) 父亲，\(y\) 为 \(b\) 儿子时，相当于我们要在 \(x\) 子树中找 \(a\)，\(y\) 子树中找 \(c\)，其答案为 \(2 \times f_x \displaystyle\sum_{b \in son_x}\displaystyle\sum_{y \in son_b}f_y\)。乘二是因为三元组是有序的，\((a,c),(c,a)\) 应该被算两遍。
这时再记 \(g_{u,u\in black}=\displaystyle\sum_{x\in son_u}f_x\)，\(h_{u,u\in white}=\displaystyle\sum_{x \in son_u}g_x\)。
那么分析一下 \(f\) 相当于一级儿子，\(g\) 为二级儿子，\(h\) 为三级儿子。每次删除一个点会影响他的一级儿子与他的上三级父亲，对于儿子，每个点只会被更新一遍，总复杂度 \(O(n)\)，对父亲每次只有 \(3\) 个，复杂度 \(O(1)\)。故全局复杂度 \(O(n)\)。更新把 \(h,g,f\) 更新即可。
code
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,vis[200005],ffa[400005],fa[400005];
ll ans,f[400005],g[400005],h[400005];
vector<int>e[400005];
int root(int x){
if(x==fa[x])return x;
return fa[x]=root(fa[x]);
}
ll qur(int x){
if(!x)return 0;
return (f[x]+1)*f[x]*(f[x]-1)-f[x]*f[x]+2*f[x]*h[x];//统计一个点的答案
}
void dfs(int u,int ft){
ffa[u]=ft;
for(auto v:e[u]){
if(v==ft)continue;
dfs(v,u);
if(u<=n)g[u]+=f[v];
else{
f[u]++;
h[u]+=g[v];
}
}
}
void del(int u){
int f1=root(ffa[u]),f2=ffa[f1],f3=root(ffa[f2]);
ans-=g[u]*g[u];
ans-=qur(f1)+g[f2]*g[f2]+qur(f3);
f[f1]--;g[f2]--;h[f3]--;
for(auto v:e[u]){
if(v==ffa[u])continue;
ans-=qur(v);
fa[v]=f1;
f[f1]+=f[v];
g[f2]+=f[v];
h[f1]-=f[v];h[f1]+=h[v];
h[f3]+=f[v];
}
ans+=qur(f1)+g[f2]*g[f2]+qur(f3);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int a,b;
cin>>a>>b;
e[a].pb(n+i);e[n+i].pb(a);
e[b].pb(n+i);e[n+i].pb(b);
}
dfs(n,0);
for(int i=1;i<=n;++i)ans+=g[i]*g[i];
for(int i=n+1;i<=2*n-1;++i)ans+=qur(i);
for(int i=n+1;i<=2*n-1;++i)fa[i]=i;
cout<<ans<<endl;
for(int i=1;i<n;++i){
del(i);//每次先删点进行更新
cout<<ans<<endl;
}
return 0;
}