题解：动态树的三元组计数

问题转化

初始一棵 $n$ 个节点的树，按顺序删除节点 $i$，删除时将该节点的所有存活邻居两两连边（形成团）。求每次删除前，有序三元组 $(a,b,c)$ 的数量，满足 $a,b,c$ 存活且 $a-b$、$b-c$ 在当前图中相邻。

核心思路

三元组 $(a,b,c)$ 等价于一条长度为 $2$ 的路径，中间点为 $b$，两端 $a$ 和 $c$ 是 $b$ 的不同邻居。因此答案为 $\sum_b deg(b)\cdot (deg(b)-1)$，其中 $deg(b)$ 是 $b$ 在当前图中的度数。

动态维护

删除节点 $x$ 时：

1. $x$ 的所有存活邻居 $y$ 会互相连接，因此每个 $y$ 的度数变化为：$deg(y) \leftarrow deg(y) - 1 + (k-1)$，其中 $k$ 是 $x$ 的存活邻居数（因为 $y$ 失去 $x$ 这条边，但获得与其他 $k-1$ 个邻居的边）。
2. 更新贡献：$deg(y)$ 变化时，$deg(y)\cdot (deg(y)-1)$ 随之改变。
3. 删除 $x$ 后，$x$ 不再贡献。

数据结构

使用并查集维护“团合并”。当节点被删除时，其邻居们形成一个团，可以将它们合并为一个“超点”，用并查集维护超点的大小和度数。

实际上，删除 $x$ 后，$x$ 的所有邻居合并为一个新节点（代表一个团），该新节点的度数为原邻居度数之和减去 $2\cdot$ 内部边数。

实现方法

倒序处理：从空图开始，按 $n,n-1,\dots,1$ 的顺序加入节点 $i$。加入 $i$ 时，将 $i$ 与所有已有邻居（即原树中 $i$ 的编号更大的邻居）所在超点连接，并更新答案。

维护：

• $cnt[u]$：超点 $u$ 的原始节点个数
• $deg[u]$：超点 $u$ 的度数
• 答案贡献为 $\sum_u cnt[u] \cdot deg[u] \cdot (deg[u]-1)$

加入 $i$ 时，设 $i$ 的邻居超点集合为 $S$，将它们合并为一个新超点 $v$，$cnt[v] = 1 + \sum_{u\in S} cnt[u]$，$deg[v] = \sum_{u\in S} deg[u] - |S|$（因为内部边不计入度数）。然后更新答案。

复杂度

并查集维护，$O(n \alpha(n))$。