Description
给定一棵初始有 \(n\) 个点的树。
在第 \(i\) 天，这棵树的第 \(i\) 个点会被删除，所有与点 \(i\) 直接相连的点之间都会两两连上一条边。你需要在每次删点发生前，求出满足 \((a,b)\) 之间有边，\((b,c)\) 之间有边且 \(a\not=c\)的有序三元组 \((a,b,c)\) 对数。
\(n\leq 2\times 10^5\)。
Solution
考虑把每个原图中的点看成白点，边看成黑点，原图中有连边的两个点就向他们对应的黑点连边。
那么每次删点操作就相当于把一个白点的所有相邻黑点合并，并且删除这个黑点。
所以所有 \((a,b,c)\) 可以看成 \((a,x,b,y,c)\)，其中 \(x\) 是 \(a,b\) 连边对应的黑点，\(y\) 是 \(b,c\) 连边对应的黑点。
容易发现把 \(n\) 作为根可以保证图始终是个树。
设 \(s_x\) 表示 \(x\) 的儿子数，\(t_x\) 表示 \(x\) 儿子的 \(s\) 之和，\(w_x\) 表示 \(x\) 儿子的 \(t\) 之和。然后考虑分类讨论。
首先如果 \(x=y\)，答案就是 \(\sum_{x为黑点}{(s_x+1)s_x(s_x-1)}\)。
如果 \(x\neq y\) 但是 \(x,y\) 都是 \(b\) 的儿子，答案就是 \(\sum_{b为白点}{\left(t_b^2-\sum_{x\in son(b)}{s_x^2}\right)}\)。
最后就是 \(x\neq y\) 且 \(x,y\) 一个是 \(b\) 的儿子，一个是 \(b\) 的父亲。
答案就是 \(2\sum_{x是黑点}{s_x w_x}\)。
把所有的加起来就是：
\[\sum_{x是黑点}{s_x^3-s_x^2-s_x+2s_x w_x}+\sum_{y是白点}{t_y^2} \]每次合并的时候用并查集维护即可。
时间复杂度：\(O(n\log n)\)。
Code
还没调出来。
标签：连边,USACO23OPEN,黑点,题解,sum,白点,儿子,Cows From： https://www.cnblogs.com/Scarab/p/17823055.html