题目链接: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到根节点的异或值。
然后考虑两种情况:
- u,v的LCA为根节点(u,v在不同的链上)。
- 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;
}