2019西安邀请赛J题解析：树形动态规划求解异或路径问题

题目背景与链接

本题源自2019年西安邀请赛，题目编号为J。题目要求在给定的一棵树中，找到所有子路径的集合，使得这些子路径的异或值为0。

问题分析：

若仅需计算异或值为0的路径数量，则此问题相对简单。但本题进一步要求计算满足条件的路径集合的数量，这需要我们从基础问题出发进行扩展思考。具体来说，我们需要计算的是树中所有可能的子路径中，哪些子路径的异或值为0。这本质上是一个计数问题，利用异或运算的一个重要性质，即任何数字与自身异或的结果为0（x^x=0），可以帮助我们设计算法。

设1为树的根节点，定义xor[i]表示从节点i到根节点路径上的异或值。对于两个不在同一条链上的节点s和e，如果它们的异或值相等，则可以推断出存在一个子路径的异或值为0，此时答案应增加size[s]*size[e]。如果两个节点位于同一链上（深度depth[e]>depth[s]），则令f为s的子节点且是e的祖先，答案应增加size[e]*(n-size[f])。由于异或值可能非常大，使用unordered_map来存储异或值及其出现次数，从而有效处理这种情况。

代码实现：

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
unordered_map mp;
ll n, sz[MAXN], Xor[MAXN], ans;
vector> adj[MAXN];

void dfs_size(int s, int pre) {
    sz[s] = 1;
    for (auto &edge : adj[s]) {
        int e = edge.first;
        if (e != pre) {
            Xor[e] = Xor[s] ^ edge.second;
            dfs_size(e, s);
            sz[s] = (sz[s] + sz[e]) % MOD;
        }
    }
}

void dfs_fork(int s, int pre) {
    ans = (ans + sz[s] * mp[Xor[s]]) % MOD;
    for (auto &edge : adj[s]) {
        int e = edge.first;
        if (e != pre)
            dfs_fork(e, s);
    }
    mp[Xor[s]] = (mp[Xor[s]] + sz[s]) % MOD;
}

void dfs_line(int s, int pre) {
    ans = (ans + mp[Xor[s]] * sz[s]) % MOD;
    for (auto &edge : adj[s]) {
        int e = edge.first;
        if (e != pre) {
            mp[Xor[s]] += (n - sz[e]);
            dfs_line(e, s);
            mp[Xor[s]] -= (n - sz[e]);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int fa;
        ll c;
        cin >> fa >> c;
        adj[fa].emplace_back(i, c);
        adj[i].emplace_back(fa, c);
    }
    dfs_size(1, -1);
    mp.clear();
    dfs_fork(1, -1);
    mp.clear();
    dfs_line(1, -1);
    cout <    return 0;
}