P9194 Triples of Cows P 题解
spider_oyster
·
·
题解
删除一个点影响太大，考虑增加一些额外结点。
把第 i 条边拆为 (u,n+i),(v,n+i)。
记原来的点是黑点，新加的点为白点。
不难发现新生成的图还是一棵树，且一个白点所连的所有黑点在原图两两有边。
考虑删除一个黑点 u，就是让 u 的子白点 v 合并到父亲白点 fa_u 上。
并查集维护即可。
考虑计算答案。不妨三元组 (a,b,c) 变为五元组 (a,x,b,y,c)，其中 x,y 为白点，其余为黑点。那么有以下情况：
设 f_x 为白点 x 的黑儿子个数，随便选三个即可，贡献 (f_x+1)\times f_x \times (f_x-1)。
枚举 x,y，贡献 \sum\limits_{x,y\in son_b,x\neq y} f_x\times f_y=(\sum\limits_{x} f_x)^2-\sum\limits_{x} f_x^2。
贡献为 2\times f_x\sum\limits_{b\in son_x} \sum\limits_{y\in son_b} f_y，前面为选 a（除 b 以外的其他儿子和 x 的父亲）的方案，后面为选 c 的方案。
若 i 为黑点，定义 g_i=\sum\limits_{j\in son_i} f_j。
若 i 为白点，定义 h_i=\sum\limits_{j\in son_i} g_i。
考虑对上面的所有情况贡献求和，那么答案为：
删除一个点 $u$，受影响的有子结点 $v$，父结点 $x$，父父结点 $y$，父父父结点 $z$。
合并 $v \rightarrow x$，维护 $f,g,h$ 值即可。
尤其注意合并时要剔除 $f_v$ 对 $t_x$ 的贡献。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
int n,ans,f[N],g[N],h[N],fa[N],F[N];
vector<int> G[N];
int find(int x) {return x==F[x]?x:F[x]=find(F[x]);}
int calc(int i) {if(!i) return 0;return (f[i]+1)*f[i]*(f[i]-1)-f[i]*f[i]+2*f[i]*h[i];}
void dfs(int u)
{
for(int v:G[u])
{
if(v==fa[u]) continue;
fa[v]=u,dfs(v);
if(u<=n) g[u]+=f[v];
else f[u]++,h[u]+=g[v];
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
G[u].push_back(n+i),G[n+i].push_back(u);
G[v].push_back(n+i),G[n+i].push_back(v);
}
dfs(n);//以 n 为根因为 n 是最后一个删除的
for(int i=1;i<=n;i++) ans+=g[i]*g[i];
for(int i=n+1;i<2*n;i++) ans+=calc(i),F[i]=i;
cout<<ans<<'\n';
for(int i=1;i<n;i++)
{
int u=i,x=find(fa[u]),y=fa[x],z=find(fa[y]);
ans-=g[u]*g[u]+calc(x)+g[y]*g[y]+calc(z);
f[x]--,g[y]--,h[z]--;
for(int v:G[u])
{
if(v==fa[u]) continue;
F[v]=x;
ans-=calc(v);
f[x]+=f[v];
h[x]-=f[v],h[x]+=h[v];
g[y]+=f[v],h[z]+=f[v];
}
ans+=calc(x)+g[y]*g[y]+calc(z);
cout<<ans<<'\n';
}
}
```