题目

题目描述：
给定一棵n个点的树，每个点有权值Ai。定义path(i,j)表示 i 到 j 的最短路径上，所有点的点权异或和。
对于i=1∼n−1, j=i+1∼n，求所有path(i,j)的异或和。

输入描述：
第一行一个整数n。
接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。

第n+1行有n个整数，表示每个点的权值Ai。

输出描述：
输出一个整数，表示所有path(i,j)的异或和，其中i=1∼n−1, j=i+1∼n。

解析

1）知识点

这道题名字是叫我们弄异或和，但重点还是树上计算。

2）看题目

题目的意思就是说，我们求出所有可能路径的异或和。路径异或和就是两个节点间最短路径的所有节点异或和。

3）算法分析

这道题只要知道两个前导知识，并对题目做出一些推理就好了。
首先我们要知道，我们不可能硬着去暴力遍历，因为我们的数据范围就有5e5，一般超过1e9的计算量直接就T了，不考虑。
然后我们如果要简化，肯定要用到一些特殊性质。
所以第一个前导小知识就是：a^a=0。简单来说，如果一个数在异或的过程中出现了偶数次，就不用算ta了，如果出现了奇数次，就和一次是一样的。
1. 所以根据这个知识点，我们接下来的想法就是说，去计算每一个点到底在全部的过程中被经过了几次。
但是每个点被经过了几次怎么算呢？这里就引入了我们的第二个前导知识：某一条边的最短路总共经过次数为sz[u] * (n - sz[u])（这个我也不知道为啥，我也要去补补了）。
1. 根据这个类似的知识点，我们怎么得到一个点的经过次数呢？
2. 经过这个点，是不是一定就会经过这旁边的一条或两条边（一条的情况是起点或终点，两条是指经过这个点的时候）？所以我们计算经过次数+ta是起点的次数（n-1）就好了。最后去重一下，就是除二。
最后备注一下我们要在dfs时求sz数组（sz[i]表示 i 节点的子树大小）用于计算边的通过次数。

4）算法操作

首先前向星就不用我说了，我也有这个专题了。

然后就是按照上面九三，这里要注意的只有怎么去计算sz数组，如下：

void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];//节点大小累加计算
    }

剩下的就按照要求计算就好了。

5）打代码

打代码嘞！
我们在这里首先要前向星初始化。
然后因为是点权，所以这里单独用一个w数组记录点权。
然后dfs遍历再输出就好了。
看我代码吧~

AC代码

#include <iostream>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int N = 5e5 + 7;
int head[N], tot;//前向星初始化数组
struct Node {
    int v, next;
} edge[N << 1];
int n, w[N], sz[N];//树的节点个数、节点权值、每个节点的子树大小
int ans;
//全局变量区

void init();//前向星初始化y
void add_edge(int u, int v);//前向星加带权边
void dfs(int u, int fa);//前向星dfs
//函数预定义区

int main() {
    IOS;
    cin >> n;
    init();
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    for (int i = 1; i <= n; i++) cin >> w[i];

    ans = 0;
    dfs(1, 0);

    cout << ans << endl;
    return 0;
}
void init() {
    memset(head, 0, sizeof head); tot = 0;
}
void add_edge(int u, int v) {
    tot++;
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    sz[u] = 1;
    int num = n - 1;//计数经过此处，初始化为以他开始的最短路条数（从u到其他点有n-1种最短路）
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
        num += sz[v] * (n - sz[v]);//计算u->v边的经过数量
        sz[u] += sz[v];//节点大小累加计算
    }
    num += sz[u] * (n - sz[u]);//计算fa->u边的经过数量
    //点的经过数量就是边的经过数量之和，最后去重就可以了
    num /= 2;//去重
    if (num & 1) ans ^= w[u];
}
//函数区

【每日一题】Xor Path

题目

解析