本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 20:33:30

思路

设任意一个点 $u$，$dis_{u,x} \oplus dis_{u,y} = k$

• 预先转化
  $u \rightarrow x$ 和 $u \rightarrow y$ 两条路径肯定有一段重复的，然后在 $x \rightarrow y$ 的链上的某个点 $t$ 分开，现在要计算的只剩下 $x \rightarrow y$ 的链上的点。设 $s_i$ 代表根节点到当前点的异或和（$dis_{1,i}$)，一个暂时的答案是 $s_x \oplus s_y$
• 上一步中有些还没考虑到
  如 $lca_{x,y}$ 在 $x \rightarrow y$ 的链上，是有贡献的（在 $lca_{x,y}$ 不等于 $t$ 的情况下），但是异或之后没了，所以需要再次异或加上。而 $t$ 是没有贡献的，应该再异或一次删掉（如果 $lca_{x,y} = t$，那么会导致多异或一下，下面会解释）
• 解释一下上一步
  如果 $lca_{x,y}$ 等于 $t$（也就是说路径在 $lca_{x,y}$ 分开，这样$lca_{x,y}$ 就没有贡献了）,那么也可以直接异或，因为这样 $lca_{x,y}$ 部分多异或了一下，$t$ 部分多异或了一下，异或两次相当于没异或，又对了
• 总结第二步
  $dis_{u,x} \oplus dis_{u,y} = k$ 转化为：
  $s_x \oplus s_y \oplus w_{lca_{x,y}} \oplus w_t = k$
  继续转化：
  $w_t = k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}} $

问题转化为，$x \rightarrow y$ 的链上是否有一个点，权值是 $k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}$ ，也就是统计 $x \rightarrow y$ 这条链上权值为 $k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}$ 的点的数量（注意这个权值仅仅是当前询问对应的！）
对于每一组这样的 $x,y$ ，设 $z_i$ 表示从 $1$ 到 $i$ 点权值为 $k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}$ 的数量 （注意这个 $z_i$ 仅仅是当前询问对应的 $z_i$ ！），答案就是 $z_x + z_y - z_{lca_{x,y}} - z_{lca_{x,y}.father}$。把所有询问离线一下，将 $x,y,lca_{x,y},lca_{x,y}.father$ 在树上做一下标记，dfs 的时候集中处理
dfs 具体如下：
dfs 前打标记部分：在树上指定部分标上 +1 或 -1，代表这次询问要加上还是减去这个点的贡献。
dfs 部分：设当前 dfs 到了点 $u$，那么将该点权值对应的 $z_u$ 乘上该点标记加到对应的询问里去。

最后看每个询问的值是否大于 0 就行了

注意：

$z_i$ 并不需要预先求出，dfs 的时候每递归到一个点，就将其对应的 $z_i$ 更新一下就行了。

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=5e5+5;
	int n,m;
	int w[maxn];
	int head[maxn];
	struct EDGE
	{
		int to,nxt;
	}edge[maxn<<1];
	int cnt;
	inline void add(int u,int to)
	{
		edge[++cnt].to=to;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int fa[20][maxn];
	int dep[maxn];
	int s[maxn];
	void dfs(int u,int _fa)
	{
		s[u]=s[_fa]^w[u];
		dep[u]=dep[_fa]+1;
		fa[0][u]=_fa;
		for(int i=1;i<=19;i++)
		{
			fa[i][u]=fa[i-1][fa[i-1][u]];
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs(to,u);
		}
	}
	inline int lca(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		for(int i=19;i>=0;i--)
		{
			if(dep[fa[i][x]]>=dep[y])
			{
				x=fa[i][x];
			}
		}
		if(x==y)return x;
		for(int i=19;i>=0;i--)
		{
			if(fa[i][x]!=fa[i][y])
			{
				x=fa[i][x];
				y=fa[i][y];
			}
		}
		return fa[0][x];
	}
	int t[maxn];
	vector<pair<int,int> > tag[maxn]; 
	int tot[10000005];
	int count[maxn];
	void dfs2(int u,int _fa)
	{
		tot[w[u]]++;
		for(int i=0;i<tag[u].size();i++)
		{
			int id=tag[u][i].first;
			int w=tag[u][i].second;
			count[id]+=w*tot[t[id]];
		} 
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs2(to,u);
		}
		tot[w[u]]--;\/\/退出当前链，记得清除标记 
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&w[i]);
		}
		for(int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
		dfs(1,0);
		for(int i=1;i<=m;i++)
		{
			int a,b,k;
			scanf("%d%d%d",&a,&b,&k);
			int _lca=lca(a,b);
			t[i]=k^s[a]^s[b]^w[_lca];
			if(t[i]>1e7)continue;
			tag[a].emplace_back(make_pair(i,1));
			tag[b].emplace_back(make_pair(i,1));
			tag[_lca].emplace_back(make_pair(i,-1));
			tag[fa[0][_lca]].emplace_back(make_pair(i,-1));
		}
		dfs2(1,0);
		for(int i=1;i<=m;i++)
		{
			if(count[i]>0)
			{
				printf("Yes\n");
			}
			else 
			{
				printf("No\n");
			}
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

参考博客

一扶苏一的博客