题目

题目描述

众所周知，一株马齿苋是活的，当且仅当它是连通的
特别地，一株活马齿苋上有$n$个独立的节点，以及连接这些点的$n-1$条苋边。每条苋边有一个值，定义为苋边的键值
对于一株马齿苋，我们定义两点间的简单路径为其相互到达所经过的最短苋路径
生物学界对于马齿苋的性质有许多研究，其中生物学家Pauling在其$1995$年的一篇论文中提到过这样一个经典问题：给定一株马齿苋上的一条简单路径，用生物方法判断路径上键值的异或和是否为$k$
这里尝试对这个问题进行推广，称之为泛马齿苋问题：给定一株马齿苋，求有多少条简单路径，使得路径上键值的异或和为$k$

输入格式

第一行，两个整数$n,k$
以下$n$行$a,b,c$表示$a\rightarrow b$有边，其键值

为$c$

输出格式

一个数，即答案

样例

样例输入

样例输出

数据范围与提示

对于$30%$的数据，$1\leqslant n\leqslant 100,k\leqslant10$
对于$50%$的数据，$1\leqslant n\leqslant 2000,k\leqslant 256$
对于$100%$的数据，$1\leqslant n\leqslant 4\times 10^5,k\leqslant 10^9$

题解

由于这是一棵树，所以简单路径就是没有重复经过一个点的路径
设$f(u,v)$为从$u$到$v$的简单路径的异或和
由异或的性质：$a\land a=1$可以知道，$f(u,v)=f(1,u)\land f(1,v)$
所以，我们可以先预处理出所有的$f(1,u)$
又因为$a\land b=c$可以推出$a\land c=b$，所以，我们只需要统计所有$f(1,u)\land k=f(1,v)$的$u$和$v$就可以了
注意：用map离散化，答案要除以2
附上代码：

#include<cstdio>
#include<map>
using namespace std;
map<int,int> d;
int n,k,tot,sum,head[400010],nxt[800010],to[800010],ver[800010],XOR[400010],s[400010];
long long ans;
void add(int u,int v,int w)
{
    nxt[++tot]=head[u],head[u]=tot,to[tot]=v,ver[tot]=w;
}
void dfs(int x,int fa)
{
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa) XOR[to[i]]=XOR[x]^ver[i],dfs(to[i],x);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,u,v,w;i<n;i++) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
    dfs(1,0);
    for(int i=1;i<=n;i++) if(!d[XOR[i]]) d[XOR[i]]=++sum;
    for(int i=1;i<=n;i++) s[d[XOR[i]]]++;
    for(int i=1;i<=n;i++) ans+=s[d[XOR[i]^k]];
    printf("%lld",ans/2);
}