题目链接：The 2019 ACM-ICPC China Shannxi Provincial Programming Contest-J. And And And

题意：

给定一棵树，树边上有边权，定义：X(u,v)表示u点到v点路径上的边权异或值，E(u,v)表示u点到v点的路径。要求计算：

$$ \Sigma_{u=1}^{n}\Sigma_{v=1}^{n}\Sigma_{u'\in E(u,v)}\Sigma_{v'\in E(u,v)}[u<v][u'<v'][X(u',v')=0] $$

题解：

题目可以从 u到v这条链上的异或值等于0 转化为 u到根节点的异或值=v到根节点的异或值。

然后考虑两种情况：

1. u，v的LCA为根节点（u，v在不同的链上）。
2. u，v的LCA为u或者v（u，v在同一条链上）。

对于情况一：我们只需要找到一对X(u,v)=0，然后对答案进行计数即可（siz[u]*siz[v]）

对于情况二：子树大小不一定是我们预处理出来的情况，所以需要记录一个新变量来记录。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 6;
const LL mod = 1000000007;
int n;
struct EDGE
{
    int v, nxt;
    LL w;
} edge[MAXN << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v, LL w)
{
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
LL ans = 0;
int siz[MAXN];
unordered_map<LL, int> mp; //到根节点异或值为k的子树的大小
void dfs(int u, int Fa)    //预处理出子树大小
{
    siz[u] = 1;
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (v == Fa)
            continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}
//不同链
void dfs1(int u, int Fa, LL k)
{
    ans = (ans + 1LL * siz[u] * mp[k]) % mod;
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        LL w = edge[i].w;
        if (v == Fa)
            continue;
        dfs1(v, u, k ^ w);
    }
    mp[k] = (mp[k] + siz[u]) % mod;
}
//同链
LL sum = 0;
void dfs2(int u, int Fa, LL k)
{
    ans = (ans + 1LL * siz[u] * mp[k]) % mod;
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        LL w = edge[i].w;
        if (v == Fa)
            continue;
        sum = (sum + siz[u] - siz[v]) % mod;
        mp[k] = (mp[k] + sum) % mod;
        dfs2(v, u, k ^ w);
        mp[k] = (mp[k] - sum) % mod;
        sum = (sum - siz[u] + siz[v]) % mod;
    }
}
int main()
{
    scanf("%d", &n);
    ecnt = 0;
    mp.clear();
    memset(fir, -1, sizeof(fir));
    for (int i = 2; i <= n; i++)
    {
        int v;
        LL w;
        scanf("%d%lld", &v, &w);
        addedge(i, v, w);
        addedge(v, i, w);
    }
    dfs(1, -1);
    dfs1(1, -1, 0);
    mp.clear();
    dfs2(1, -1, 0);
    printf("%lld\n", ans);
    return 0;
}