WA on #1 求条

#include <bits/stdc++.h>
using namespace std;

const long long N = 500005;
long long n , m , len , w[N] , pre[N] , dep[N] , dis[N] , be[N] , siz[N] , son[N] , top[N] , st[N] , ed[N] , pos[N] , num = 0 , tot[10000005] , vis[N];
bool ans[N];
vector <long long> g[N];

long long read()
{
	long long f = 1 , res = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		res = res * 10 + ch - '0';
		ch = getchar();
	}
	return f * res;
}

struct query
{
	long long x , y , k , id , LCA;
};
query q[N];
long long cnt = 0;
bool cmp(query a , query b) {return (be[a.x] ^ be[b.x] ? a.x < b.x : (be[a.x] & 1 ? a.y < b.y : a.y > b.y));}

void dfs1(long long u , long long fa)
{
	siz[u] = 1;
	pre[u] = fa;
	dis[u] = dis[fa] ^ w[u];
	dep[u] = dep[fa] + 1;
	for(auto v : g[u])
	{
		if(v == fa) continue;
		dfs1(v , u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]]) son[u] = v;
	}
}

void dfs2(long long u , long long fa)
{
	st[u] = ++num;
	pos[num] = u;
	be[num] = (num - 1) / len + 1;
	if(!son[u]) return;
	top[son[u]] = top[u];
	dfs2(son[u] , u);
	for(auto v : g[u])
	{
		if(v == fa || v == son[u]) continue;
		top[v] = v;
		dfs2(v , u);
	}
	ed[u] = ++num;
	pos[num] = u;
	be[num] = (num - 1) / len + 1;
}

long long lca(long long u , long long v)
{
	while(top[u] != top[v])
	{
		if(dep[u] < dep[v]) swap(u , v);
		u = pre[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

void add(long long x)
{
	vis[pos[x]] ^= 1;
	if(vis[pos[x]]) tot[w[pos[x]]]++;
	else tot[w[pos[x]]]--;
}

int main()
{
	// freopen("P8201.in" , "r" , stdin);
	// freopen("P8201.out" , "w" , stdout);
	cin.tie(nullptr)->sync_with_stdio(false);
	n = read(); m = read();
	len = pow(n * 2 , 0.6);
	for(long long i = 1 ; i <= n ; i++) w[i] = read();
	long long u , v;
	for(long long i = 1 ; i < n ; i++){u = read(); v = read(); g[u].push_back(v); g[v].push_back(u);}
	sort(q + 1 , q + cnt + 1 , cmp);
	dfs1(1 , 1);
	top[1] = 1;
	dfs2(1 , 1);
	for(long long i = 1 , k ; i <= m ; i++)
	{
		u = read(); v = read(); k = read();
		if(st[u] > st[v])
		{
			swap(u , v);
		}
		long long LCA = lca(u , v);
		k = k ^ dis[u] ^ dis[v] ^ w[LCA];
		q[++cnt].x = (LCA == u ? st[u] : ed[u]);
		q[cnt].y = st[v];
		q[cnt].k = k;
		q[cnt].id = i;
		q[cnt].LCA = LCA;
		if(w[LCA] == q[cnt].k) {ans[i] = 1; cnt--;}
	}
	u = 1 , v = 0;
	for(long long i = 1 ; i <= cnt ; i++)
	{
		while(u < q[i].x) add(u++);
		while(u > q[i].x) add(--u);
		while(v < q[i].y) add(++v);
		while(v > q[i].y) add(v--);
		ans[q[i].id] = tot[q[i].k];
	}
	for(long long i = 1 ; i <= m ; i++) cout << (ans[i] ? "yes\n" : "no\n");
	return 0;
}