自动搬运

查看原文

来自洛谷，原作者为

	by_chance 还好我拥有不同的宇宙，能治愈所有我偏执的梦。

搬运于2025-08-24 22:46:13，当前版本为作者最后更新于2023-05-23 21:58:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Link

由于每次删点之后新增的边数太多，所以考虑拆边。用一个白点表示一条边，并将原来树中的点称为黑点，编号不变。对于第 $i$ 条边 $(u_i,v_i)$，在 $(u_i,n+i),(v_i,n+i)$ 间连边，得到一棵树 $T$。

删除点 $i$ 时，我们将点 $i$ 相邻的所有白点合并为一个点，然后删除 $i$。容易归纳证明：每次删除后 $T$ 仍然是树；真实的 $u,v$ 间有边等价于树 $T$ 中存在一个白点与 $u,v$ 均相邻。

因为依次删除 $1,2,...,n$，所以在树 $T$ 中，可以把点 $n$ 作为根。这样每次删除时，就可以把 $i$ 的所有相邻白点合并到 $i$ 的父亲白点上去。然后，用并查集维护每个白点被合并到了哪个点。

用 $fa_u$ 表示在初始的 $T$ 中 $u$ 的父亲结点，$p_u$ 表示某个时刻白点 $u$ 被合并到的点。那么，在这一时刻，黑点 $u$ 的父亲结点是 $p_{fa_u}$，白点 $u$ 的父亲节点是 $fa_{p_u}$。

下面来考虑如何统计答案。对白点 $u$，记 $s_u$ 为 $u$ 的儿子个数。

对于一个符合要求的 $(a,b,c)$，设 $a,b$ 通过白点 $x$ 相连，$b,c$ 通过白点 $y$ 相连。

1. 如果 $x=y$：固定 $x$，在 $x$ 的邻点中任选 $3$ 个，则对答案的贡献为$$\sum_{x} (s_x+1)s_x(s_x-1)$$ 求和的条件是 $x$ 是白点。
2. 如果 $x\not=y$，且 $x,y$ 都是 $b$ 的子节点：固定 $b$，先任取 $b$ 的两个子结点 $x,y$，此时贡献 $s_xs_y$。则总的贡献为$$\sum_{b} (\sum_{x} s_x) ^2 - \sum_{x} s_x^2$$ 第一个求和的条件是 $b$ 是黑点，后两个求和的条件是 $x$ 是 $b$ 的儿子。 注意到后一项拆出来就是对所有白点 $x$ 求 $s_x^2$ 的和，那就拆出来吧。
3. 如果 $x\not=y$，且 $x,y$ 一个是 $b$ 的子结点，另一个是 $b$ 的父亲结点：不妨 $x$ 是 $b$ 的父亲结点，固定 $x$，$b$ 是 $x$ 的一个子结点，$y$ 又是 $b$ 的一个子结点，则对答案的贡献为$$\sum_{x} 2\times s_x \times \sum_{b} \sum_{y} s_y$$ 三个求和的条件分别为 $x$ 是白点，$b$ 是 $x$ 的子结点，$y$ 是 $b$ 的结点。

列出式子后，我们发现需要维护以下数据：

1. 白点 $u$ 的儿子数目 $s_u$
2. 黑点 $u$ 的儿子的 $s$ 值之和，也可以存到数组 $s$ 里
3. 白点 $u$ 的儿子的 $s$ 值之和 $t_u$

答案是 $\sum_{x}(f(s_x)+2s_xt_x)+\sum_{y} s_y^2$，其中 $f(x)=x^3-x^2-x$，两个求和的条件分别是 $x$ 是黑点，$y$ 是白点。

删除点 $u$ 时，枚举它初始的的儿子（一定没有被合并过），在并查集中将其合并到 $u$ 的父亲中。然后清零 $u$ 和 $u$ 的儿子的值，更新 $u$ 的三层祖先的值，并更新答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
int n,fa[N],p[N];ll s[N],t[N],ans;
int head[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
void dfs(int u){
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]){
			fa[v]=u;dfs(v);
			if(u<=n)s[u]+=s[v];
			else ++s[u],t[u]+=s[v];
		}
}
int find(int x){return (x==p[x]?x:(p[x]=find(p[x])));}
ll f(ll x){return x*x*x-x*x-x;}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,n+i);add(v,n+i);add(n+i,u);add(n+i,v);
	}
	dfs(n);
	for(int i=1;i<2*n;i++)p[i]=i;
	for(int i=1;i<=n;i++)ans+=s[i]*s[i];
	for(int i=n+1;i<2*n;i++)ans+=f(s[i])+2*s[i]*t[i];
	for(int u=1;u<=n;u++){
		printf("%lld\n",ans);
		int g=find(fa[u]),w=fa[g];ll del=-1;
		ans-=f(s[g])+2*s[g]*t[g]+s[w]*s[w];s[w]-=s[g];--s[g];
		t[g]-=s[u];ans-=s[u]*s[u];s[u]=0;
		for(int i=head[u],v;i;i=nxt[i])
			if((v=ver[i])!=fa[u]){
				p[v]=g;s[g]+=s[v];t[g]+=t[v];del+=s[v];
				ans-=f(s[v])+2*s[v]*t[v];s[v]=t[v]=0;
			}
		s[w]+=s[g];ans+=f(s[g])+2*s[g]*t[g]+s[w]*s[w];
		t[w=find(fa[fa[g]])]+=del;ans+=2*s[w]*del;
	}
	return 0;
}

Upd：修改了格式。