关键观察

题目要求的三元组 $(i_0, i_1, i_2)$ 实际上对应树上的三条路径：

路径 $i_0 \to i_1$

路径 $i_1 \to i_2$

且这两段路径不共享任何边

这等价于三条路径在树上形成一个"Y"字形结构，$i_1$ 是分叉点。

容斥原理 总的三元组数量为： total=cnt[0]×cnt[1]×cnt[2] 其中 $\text{cnt}[t]$ 表示类型 $t$ 的节点数量。

但是需要减去不合法的三元组，即路径重复经过边的情况。

Top Tree 解法

使用 Top Tree（拓扑树）数据结构来维护树上的动态信息。Top Tree 将树分解为多个簇（cluster），每个簇维护关于路径组合的信息。

簇信息定义 对于每个簇，维护以下信息：

a, b, c：簇内各类节点的数量

abc：簇内合法的三元组数量

xbc, abx, ybc, aby, axc：各种路径组合的数量

axy, xby, yxc：其他辅助信息

yb：簇底节点是否为类型1

其中 $x$ 表示簇顶，$y$ 表示簇底。

合并操作

Top Tree 有两种基本操作：

Rake 操作：合并两个共享簇顶的簇

Compress 操作：合并两个首尾相连的簇

每种操作都有相应的信息合并公式，通过动态维护这些信息，可以在 $O(\log n)$ 时间内完成更新和查询。

复杂度分析

初始化：$O(N)$，构建 Top Tree

每次更新：$O(\log N)$，在 Top Tree 上更新一条路径

查询：$O(1)$，直接返回根簇的信息

总复杂度：$O(N + Q \log N)$

最后要注意的则是需要把grader.cpp文件里的代码复制到你的代码的后面才能通过评测。