题意：给一棵n个节点的树（无向边），有q个询问，每个询问有一个值s，问有多少点对(u,v)的xor和为s？ 注意：(u,v)和(v,u)只算一次。而且u=v也是合法的。
思路：任意点对之间的路径肯定经过LCA的，但是如果如果知道某个点t到根的路径xor和为e，那么就能够得知 x^e=s中的x应该是多少，那就算有多少点到根的xor和为x即可。e是表示t到根的，所以而x也是其他点到根的路径xor和，两个点他们的LCA到根这段会被算2次，那么xor就为0了。
（1）DFS算出每个点到根的路径xor和，相同的用一个桶装起来，复杂度O(n)。
（2）对于每个询问s，穷举树上n个点，找到另一个点到root的路径xor和，在对应桶里的都是可以组成s的。（注意要去重）
特别要注意的是，s可能为0，那么就有x^x=s的情况，另一个点也会在同一个桶里。还有，要用long long保存答案。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x7f7f7f7f
#define LL long long
using namespace std;
const int N=;
vector<int> vect[N];
struct node
{
int from,to,val;
node(){};
node(int from,int to,int val):from(from),to(to),val(val){};
}edge[N*];
int edge_cnt, n, buck[N*], self[N], vis[N], q; void add_node(int from,int to,int val)
{
edge[edge_cnt]=node(from, to, val);
vect[from].push_back(edge_cnt++);
} void DFS(int x,int sum)
{
vis[x]=;
for(int i=; i<vect[x].size(); i++)
{
node &e=edge[vect[x][i]];
if( !vis[e.to])
{
buck[ self[e.to]=sum^e.val ]++;
DFS(e.to, sum^e.val);
}
}
} LL get_ans(int a)
{
LL ans=;
if(a==)
{
for(int j=; j<=n; j++)
{
int t=self[j]; //a为0，这个桶肯定是自己的那个
ans+=buck[ t ]-; //先扣掉自己。但是仍然会算重了。它到别人，别人也会到他。
}
ans+=n*; //每个点到自己都算。
}
else //a!=0，那么不可能有两个相同数的异或和为a的。
{
for(int j=; j<=n; j++)
{
int t=a^self[j]; //这个肯定不跟j同个桶。
ans+=buck[t];
}
}
return ans/; //去重
} void cal(int n)
{
memset(vis, , sizeof(vis));
memset(buck, , sizeof(buck));
memset(self, , sizeof(self));
DFS(, );
cin>>q;
for(int i=,a=; i<q; i++)
{
scanf("%d", &a);
printf("%lld\n", get_ans(a));
}
} int main()
{
freopen("input.txt", "r", stdin);
int t, a, b, c;
cin>>t;
while(t--)
{
cin>>n;
edge_cnt=;
for(int i=; i<=n; i++) vect[i].clear();
for(int i=; i<n; i++)
{
scanf("%d%d%d", &a, &b, &c);
add_node(a,b,c);
add_node(b,a,c);
}
add_node(, , ); //虚拟的根节点，0号节点
cal(n);
}
return ;
}
AC代码
数据
2
3
1 2 1
2 3 2
3
2
3
4
4
1 2 1
2 3 2
2 4 1
4
0
1
2
3
答案：
1
1
0
5
2
1
2