ICPC2019 西安邀请赛 J.And And And
题目链接
https://nanti.jisuanke.com/t/39277
题目大意
给你一个 $n$ 个节点的树，每条边上有一个权值 $w$ ，定义 $E(u, v)$ 为路径 $u$ 到 $v$ 的点集集合， $X(u, v)$ 为路径 $u$ 到 $v$ 的所有边的权值的异或和。问
$$\sum\limits_{u=1}^{n}{\sum\limits_{v=1}^{n}{\sum\limits_{u’ \in E(u, v)}{\sum\limits_{v’ \in E(u, v)}{[u < v][u′ < v′][X(u′, v′) = 0]}}}}$$
题目分析
题目的式子很复杂……翻译过来大概是你需要统计所有异或和为 $0$ 的路径在所有点对的路径中出现额总次数。
我的一个中学的学长参加了现场赛，他们队写了个点分治，但是因为有个数组忘开 long long 导致 150 行的代码到最后都没调出来……
这道题如果用点分治来做的话思路还是很暴力的，但是写起来太麻烦而且不好调试，因此还是推荐我帮学长查代码时想出来的 $DP$ 的做法。
首先考虑到一点，如果两个点之间的路径的异或和为 $0$ ，那么他们两点到根节点的异或和应该是相等的。
那么对于两个不是祖先关系的点，显然如果他们到根节点的异或和相等，那么对答案的贡献即为他们俩各自所在子树的大小的乘积。再来考虑祖先关系的节点，他们对答案的贡献显然为更靠下的节点的子树大小和从不在子树里的点的数量的乘积。
在处理的时候，考虑 $DFS$ 的特性，在栈中的节点肯定都为当前节点的祖先，而刚进栈时其余已经经过的点肯定不为当前节点的子孙。因此在刚一进栈的时候就需要统计答案，而出栈时才计算节点对非祖先节点的可能贡献。使用 $map$ 维护一下即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 1e5 + 5;
long long mod = 1e9 + 7;
int n, m, t;
vector <int> e[maxn];
vector <long long> w[maxn];
long long sz[maxn];
map <long long, long long> f;
map <long long, long long> g;
long long ans = 0;
int dfs(int x){
sz[x] = 1;
for(int y : e[x]){
dfs(y);
sz[x] += sz[y];
}
return 0;
}
int dp(int x, long long c, long long sum){
int i, j;
int y;
ans = (ans + f[c] * sz[x]) % mod;
ans = (ans + g[c] * sz[x]) % mod;
for(i=0;i<e[x].size();i++){
y = e[x][i];
g[c] += sum + sz[x] - sz[y];
dp(y, c ^ w[x][i], sum + sz[x] - sz[y]);
g[c] -= sum + sz[x] - sz[y];
}
f[c] = (f[c] + sz[x]) % mod;
return 0;
}
int main(){
int i, j;
int x, y;
long long c;
scanf("%d", &n);
for(i=2;i<=n;i++){
scanf("%d%lld", &x, &c);
e[x].push_back(i);
w[x].push_back(c);
}
dfs(1);
dp(1, 0, 0);
printf("%lld\n", ans);
return 0;
}