A102288 雾港学宫的能量点对 题解

题意

给定一棵树，树的每条边有一个带权值的能量标记。给定两点 (u) 和 (v)，定义路径 (P(u, v)) 是从 (u) 到 (v) 的唯一简单路径，路径的能量奇偶性定义为：

$$p(u,v) = \left(\sum_{e \in P(u,v)} c_e \right) \mod 2$$

要求计算路径和为偶数的无序点对数。

---

思路与推导

1. 定义和前提

我们选定一个根（例如点 1），定义每个点 (x) 的前缀奇偶性 (d(x)) 为：

$$d(x) = \left(\sum_{e \in P(1,x)} c_e\right) \mod 2$$

即：从根 1 到 (x) 的路径上，所有边的权值和对 2 取余的结果。这个 (d(x)) 对每个点都是二值的，取值为 0 或 1。

2. 路径的奇偶性与前缀奇偶性

对于任意两点 (u) 和 (v)，它们的路径 (P(u,v)) 可以通过两条根到这两点的路径来表示：

$$P(u,v) = P(1,u) \cup 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) \oplus d(v)) \mod 2$$

即，路径的奇偶性等于两个点的前缀奇偶性的异或值。

3. 满足条件的点对

我们需要计算所有满足：

$$p(u,v) = 0$$

的点对，即：

$$d(u) = d(v)$$

这意味着，路径和为偶数的点对数量等于 (d(x)) 相同的点对数量。

4. 统计符合条件的点对数量

设：

• $(cnt_0)$ 为 (d(x) = 0) 的点数
• $(cnt_1)$ 为 (d(x) = 1) 的点数

那么，路径和为偶数的点对数量为：

$$\binom{cnt_0}{2} + \binom{cnt_1}{2}$$

即，分别统计 (d(x) = 0) 和 (d(x) = 1) 的点对数量，计算组合数即可。

5. 算法

• 使用 DFS 或 BFS 遍历树，计算每个点的前缀奇偶性 (d(x))。
• 统计 (d(x)) 为 0 和 1 的点数。
• 计算满足条件的点对数量。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        int w = (int)(c & 1LL);  // 只考虑奇偶
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> vis(n + 1, 0);
    vector<int> d(n + 1, 0);  // 到根的前缀奇偶性

    // 使用栈进行 DFS
    stack<int> st;
    st.push(1);
    vis[1] = 1;
    d[1] = 0;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        for (auto [v, w] : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                d[v] = d[u] ^ w;
                st.push(v);
            }
        }
    }

    long long cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) cnt0++;
        else cnt1++;
    }

    auto C2 = [](long long x) -> long long {
        return x * (x - 1) / 2;
    };

    cout << C2(cnt0) + C2(cnt1) << "\n";
    return 0;
}

---

时间复杂度分析

• DFS/BFS遍历树：需要 (O(n)) 时间，遍历每个节点和边一次。
• 统计组合数：(O(1))，只需要对 $(cnt_0) 和 (cnt_1)$ 计算组合数。
• 总复杂度：(O(n))，适合 $(n \le 2 \times 10^5)$。

---

样例解释

输入：

5
1 2 1
2 3 2
2 4 3
4 5 4

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. 计算点对数：

   • $(C_2(3) = 3)$
   • $(C_2(2) = 1)$
   • $总点对数 = (3 + 1 = 4)$

输出：

4

---

总结

通过树上每个点的前缀奇偶性，可以在 (O(n)) 时间内计算出符合条件的无序点对数量。通过 DFS 或 BFS 遍历树，使用异或操作计算每个点的前缀奇偶性，最后根据相同前缀奇偶性点对的组合数得到答案。