更好的阅读体验

---

我们发现一棵树删掉一个点之后会在删掉点的位置形成一个团，这很坏。我们希望还能形成一棵树。

所以我们考虑对这个图建圆方树。

我们以 $n$ 为根，这样这个点不会被删掉。然后假设方点 $u$ 的儿子个数为 $s_u$。

考虑题目要我们数的三元组 $(a, b, c)$ 的数量。假设圆点 $a, b$ 中间是方点 $x$，$b, c$ 之间方点是 $y$，那么考虑按照以下讨论来统计答案：

1. $x = y$。那么枚举这个方点，在它的邻居中随便选三个点都可以。它有 $s_x + 1$ 个邻居，那么方案数是 $(s_x + 1) s_x (s_x - 1)$。
2. $x \not = y$ 且 $x, y$ 都是 $b$ 的儿子，如图。

那么我们要数的就是在 $b$ 的孙子中挑选出两个圆点 $a, c$ 且 $a, c$ 在 $b$ 的不同子树。那就是在 $b$ 的孙子中随便挑两个的方案数，减去在每个子树里挑两个孙子的方案数。也就是

$$(\sum_{x \isin son_b} s_x) ^ 2 - \sum_{x \isin son_b} s_x ^ 2$$

对于后半部分，对于所有 $b$，每个 $x$ 只会被计算一次，所以可以拆出来。

在这种情况下，我们需要知道一个圆点 $u$ 的所有儿子的 $s$ 之和。这个我们称为 $S_u$，只有圆点有定义。在实现中我把 $S$ 和 $s$ 存在同一个数组里。

3. $x \not = y$ 且 $x, y$ 不都是 $b$ 的儿子，如图。

我们不妨假设 $b$ 的父亲是 $x$，最后 $\times 2$ 就能得到另一半的方案数。那么我们考虑在 $x$ 处计算贡献。

首先我们要先选出 $b$，然后再选出 $y$，在 $b, y$ 确定的情况下，选出 $c$ 的方案数也就是 $y$ 的儿子数量 $s_y$。然后我们还要选出 $a$。由于 $x$ 有 $s_x + 1$ 个邻居，有一个是 $b$ 已经被选择了，所以选 $a$ 的方案数是 $s_x$。所以 $x$ 的贡献是

$$2 s_x \sum_{b \isin son_x} \sum_{y \isin son_b} s_y$$

我们发现在这种情况下，我们需要知道一个方点孙子的 $s$ 之和，不妨设 $x$ 孙子的 $s$ 之和为 $t_x$。

所以综合以上三种情况，为了让式子比较好看，我们假设 $f(x) = x^3 - x^2 - x$，那么答案就是

$$\sum_x(f(s_x) + 2s_x t_x) + \sum_b S_b^2$$

$x$ 是方点，$b$ 是圆点。只要我们能动态维护 $s_x, t_x, S_b$，这道题就做完了。

---

我们考虑删点的时候是在做什么。当我们删掉一个圆点，我们会把它邻居的所有方点合并，也就是把它的儿子全部合并到它的父亲上。

这个复杂度可能不太对，因为它的儿子这个时候可能有一些也是从下面合并上来的，所以合并次数之和不一定是 $O(n)$ 的。但是我们发现我们可以在合并 $v \to u$ 时，把合并产生的贡献挂在 $u$ 上，类似于打标记，等下次 $u$ 合并到另外一个结点时，把这个标记再复制到另外一个结点。

所以我们只需要对原圆方树上的点的儿子进行合并即可，也就是对没合并过的儿子进行合并。这样一个儿子只就合并一次，复杂度就对了。

我们一次删点 $u$ 要删除 $u$ 的每个儿子，并且要更新 $u$ 的父亲，爷爷，曾祖父的权值。第一部分的和是 $O(n)$ 的，第二部分是 $O(1)$ 的。这一部分细节比较多，代码里有注释说每一步在做什么。

并查集维护即可。每次合并后更新答案。

那么这道题就做完了，复杂度 $O(n \alpha(n))$。

#include<bits/stdc++.h>
#define endl '\n'
#define N 400006
using namespace std;
using i64=long long;
int n,s[N],t[N],f[N],fa[N];
vector<int> G[N]; i64 ans;
inline void add(int u,int v) {G[u].push_back(v),G[v].push_back(u);}
inline int find(int k) {return f[k]==k?k:f[k]=find(f[k]);}
void dfs(int u)
{
	for(int v:G[u])if(v!=fa[u])
	{
		fa[v]=u,dfs(v);
		if(u>n)s[u]++,t[u]+=s[v];
		else s[u]+=s[v];
	}
}
inline i64 fc(int x) {return -1ll*x*x-x+1ll*x*x*x;}
inline i64 calc(int i) {return fc(s[i])+2ll*s[i]*t[i];}
inline void del(int u)
{
	int ft=find(fa[u]),g=fa[ft];
	//去掉父亲和爷爷的贡献 
	ans-=calc(ft)+1ll*s[g]*s[g],s[g]-=s[ft],s[ft]--;
	//去掉自己的贡献 
	t[ft]-=s[u],ans-=1ll*s[u]*s[u],s[u]=0; int ss=-1;
	//ss 表示 u 的父亲的 s 增加了多少 
	//初始为 -1 是因为 u 的父亲的 s 减掉了 u 一个 
	for(int v:G[u])if(v!=fa[u])
		//把 u 的儿子方点 v 删掉，并入 u 的父亲
		f[v]=ft,s[ft]+=s[v],ss+=s[v],t[ft]+=t[v],ans-=calc(v),s[v]=t[v]=0;
	//u 的父亲 s 增加多少，u 的爷爷 s 就增加多少，u 的曾祖父的 t 就增加增加多少
	s[g]+=s[ft],ans+=calc(ft)+1ll*s[g]*s[g];
	//更新曾祖父 
	int gg=find(fa[fa[ft]]); t[gg]+=ss,ans+=2ll*s[gg]*ss; 
}
main()
{
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
		scanf("%d%d",&u,&v),add(u,i+n),add(v,i+n);
	dfs(n);
	for(int i=1;i<=n;i++)ans+=1ll*s[i]*s[i],f[i]=i;
	for(int i=n+1;i<n*2;i++)ans+=calc(i),f[i]=i;
	printf("%lld\n",ans);
	for(int i=1;i<n;i++)del(i),printf("%lld\n",ans);
	return 0;
}
/*
考虑建圆方树。
对于点对 (a, b, c)，假设连接 ab 的方点是 x，连接 bc 的方点是 y。

假设方点 i 的儿子个数为 s[i] 

1. x = y，答案是 \sum _x (s[i]+1)s[i](s[i]-1)，x 为方点 
2. x \not = y 且 x，y 都是 b 的儿子。答案是
   sum_{b 为圆点} ( (\sum_x s[x]) ^ 2 - \sum_x s[x] ^ 2) x 为 b 的儿子。
3. x \not = y 且不妨设 x 是 b 的父亲，y 是 b 的儿子，最后乘 2 即可。
   sum_{x 为方点} 2 s[x] \sum_b \sum_y s[y]，b 为 x 的儿子，y 为 b 的儿子。 

我们维护： 
方点 s[u]。 
圆点 s[u] 表示其儿子（都是方点）的 s[v] 之和。
t[u] 表示方点的儿子的 s[v] 之和。 

圆方树删点用并查集维护即可。

这也太难了。 

看到一个比较方便的计算形式：
f(x) = x^3 - x^2 - x
ans = \sum_x( f(s[x]) + 2 s[x]t[x] ) + \sum_b s[b]^2
x 为方点，b 为圆点。

是不是就做完了。 
*/