题解：P9194 [USACO23OPEN] Triples of Cows P
dyc2022
·
·
题解
更好的阅读体验
我们发现一棵树删掉一个点之后会在删掉点的位置形成一个团，这很坏。我们希望还能形成一棵树。
所以我们考虑对这个图建圆方树。
我们以 n 为根，这样这个点不会被删掉。然后假设方点 u 的儿子个数为 s_u。
考虑题目要我们数的三元组 (a, b, c) 的数量。假设圆点 a, b 中间是方点 x，b, c 之间方点是 y，那么考虑按照以下讨论来统计答案：
-
-
那么我们要数的就是在 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 存在同一个数组里。
-
我们不妨假设 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
***
我们考虑删点的时候是在做什么。当我们删掉一个圆点，我们会把它邻居的所有方点合并，也就是把它的儿子全部合并到它的父亲上。
这个复杂度可能不太对，因为它的儿子这个时候可能有一些也是从下面合并上来的，所以合并次数之和不一定是 $O(n)$ 的。但是我们发现我们可以在合并 $v \to u$ 时，把合并产生的贡献挂在 $u$ 上，类似于打标记，等下次 $u$ 合并到另外一个结点时，把这个标记再复制到另外一个结点。
所以我们只需要对**原圆方树**上的点的儿子进行合并即可，也就是对没合并过的儿子进行合并。这样一个儿子只就合并一次，复杂度就对了。
我们一次删点 $u$ 要删除 $u$ 的每个儿子，并且要更新 $u$ 的父亲，爷爷，曾祖父的权值。第一部分的和是 $O(n)$ 的，第二部分是 $O(1)$ 的。这一部分细节比较多，代码里有注释说每一步在做什么。
并查集维护即可。每次合并后更新答案。
那么这道题就做完了，复杂度 $O(n \alpha(n))$。
```cpp
#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 为圆点。
是不是就做完了。
*/
```