A102288 雾港学宫的能量点对 题解
题意
给定一棵树，树的每条边有一个带权值的能量标记。给定两点 (u) 和 (v)，定义路径 (P(u, v)) 是从 (u) 到 (v) 的唯一简单路径，路径的能量奇偶性定义为：
p(u,v)=(∑e∈P(u,v)ce)mod 2p(u,v) = \left(\sum_{e \in P(u,v)} c_e \right) \mod 2 p(u,v)= e∈P(u,v)∑ ce mod2
要求计算路径和为偶数的无序点对数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路与推导
1. 定义和前提
我们选定一个根（例如点 1），定义每个点 (x) 的前缀奇偶性 (d(x)) 为：
d(x)=(∑e∈P(1,x)ce)mod 2d(x) = \left(\sum_{e \in P(1,x)} c_e\right) \mod 2 d(x)= e∈P(1,x)∑ ce mod2
即：从根 1 到 (x) 的路径上，所有边的权值和对 2 取余的结果。这个 (d(x)) 对每个点都是二值的，取值为 0 或 1。
2. 路径的奇偶性与前缀奇偶性
对于任意两点 (u) 和 (v)，它们的路径 (P(u,v)) 可以通过两条根到这两点的路径来表示：
P(u,v)=P(1,u)∪P(1,v)P(u,v) = P(1,u) \cup P(1,v) P(u,v)=P(1,u)∪P(1,v)
其中，(P(1,u)) 和 (P(1,v)) 是从根到 (u) 和 (v) 的路径，公共部分 (P(1,w)) （根到最近公共祖先 (w) 的路径）会被重复计入，因此它对奇偶性没有影响（因为 (2 \times c \equiv 0 \pmod{2})）。
最终，路径 (P(u,v)) 的奇偶性可以表示为：
p(u,v)=(d(u)⊕d(v))mod 2p(u,v) = (d(u) \oplus d(v)) \mod 2 p(u,v)=(d(u)⊕d(v))mod2
即，路径的奇偶性等于两个点的前缀奇偶性的异或值。
3. 满足条件的点对
我们需要计算所有满足：
p(u,v)=0p(u,v) = 0 p(u,v)=0
的点对，即：
d(u)=d(v)d(u) = d(v) d(u)=d(v)
这意味着，路径和为偶数的点对数量等于 (d(x)) 相同的点对数量。
4. 统计符合条件的点对数量
设：
* (cnt0)(cnt_0)(cnt0 ) 为 (d(x) = 0) 的点数
* (cnt1)(cnt_1)(cnt1 ) 为 (d(x) = 1) 的点数
那么，路径和为偶数的点对数量为：
(cnt02)+(cnt12)\binom{cnt_0}{2} + \binom{cnt_1}{2} (2cnt0 )+(2cnt1 )
即，分别统计 (d(x) = 0) 和 (d(x) = 1) 的点对数量，计算组合数即可。
5. 算法
* 使用 DFS 或 BFS 遍历树，计算每个点的前缀奇偶性 (d(x))。
* 统计 (d(x)) 为 0 和 1 的点数。
* 计算满足条件的点对数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* DFS/BFS遍历树：需要 (O(n)) 时间，遍历每个节点和边一次。
* 统计组合数：(O(1))，只需要对 (cnt0)和(cnt1)(cnt_0) 和 (cnt_1)(cnt0 )和(cnt1 ) 计算组合数。
* 总复杂度：(O(n))，适合 (n≤2×105)(n \le 2 \times 10^5)(n≤2×105)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例解释
输入：
1. 通过 DFS 计算每个点到根的前缀奇偶性 (d(x))：
* (d(1) = 0)
* (d(2) = 1)
* (d(3) = 0)
* (d(4) = 0)
* (d(5) = 1)
2. 统计 (d(x)) 为 0 的点数为 3，(d(x)) 为 1 的点数为 2。
3. 计算点对数：
* (C2(3)=3)(C_2(3) = 3)(C2 (3)=3)
* (C2(2)=1)(C_2(2) = 1)(C2 (2)=1)
* 总点对数=(3+1=4)总点对数 = (3 + 1 = 4)总点对数=(3+1=4)
输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
通过树上每个点的前缀奇偶性，可以在 (O(n)) 时间内计算出符合条件的无序点对数量。通过 DFS 或 BFS 遍历树，使用异或操作计算每个点的前缀奇偶性，最后根据相同前缀奇偶性点对的组合数得到答案。
