武侍乐队

第一行包含三个整数n,m,w，分别是夜之城可供演出的场地，武侍乐队的巡演次数，出道时的好评。

接下来的n-1行，每行两个整数p,q，表示编号为p的场地与编号为q的场地之间有一条双向边，保证场地之间连通。

接下来的一行有n个整数，表示这n个场地的人们对音乐的见解x。

接下来m行，每行三个整数u,v,s，表示巡演起点，终点，与风格。

C++(clang++11) 解法, 执行用时: 1178ms, 内存消耗: 116476K, 提交时间: 2021-04-06 13:34:39

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+10;
vector<int>v[N];
int x[N],f[N][20],dep[N],xo[N],cnt[32*N],rt[N],idx,tr[32*N][2];
void insert(int now,int pre,int val)
{
	for(int i=30;i>=0;i--)
	{
		bool v=val>>i&1;
		tr[now][v^1]=tr[pre][v^1];
		tr[now][v]=++idx;
		cnt[tr[now][v]]=cnt[tr[pre][v]]+1;
		now=tr[now][v];
		pre=tr[pre][v];
	}
}
void dfs(int u,int fa)
{
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	xo[u]=xo[fa]^x[u];
	for(int i=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1];
	for(auto i:v[u])
	{
		if(i==fa)continue;
		rt[i]=++idx;
		insert(rt[i],rt[u],x[i]);
		dfs(i,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
			
	if(x==y)return x;
	
	for(int i=19;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int query(int now,int pre,int val)
{
	int res=0;
	for(int i=30;i>=0;i--)
	{
		bool v=val>>i&1;
		if(cnt[tr[now][v^1]]>cnt[tr[pre][v^1]])
		{
			res+=1<<i;
			now=tr[now][v^1];
			pre=tr[pre][v^1];
		}
		else
		{
			now=tr[now][v];
			pre=tr[pre][v];
		}
	}
	return res;
}
int main()
{
	int n,m,w;
	scanf("%d%d%d",&n,&m,&w);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	dfs(1,0);
	while(m--)
	{
		int a,b,s;
		scanf("%d%d%d",&a,&b,&s);
		int p=lca(a,b);
		int ans=xo[a]^xo[b]^x[p];
		int ma=max({query(rt[b],rt[p],s),query(rt[a],rt[p],s),x[p]^s});
		ans=ans^ma^s;
		int res=0;
		for(int k=30;~k;--k)if(!(ans&(1<<k))&&res+(1<<k)<=w)res+=(1<<k);
		cout<<(ans^res)<<endl;
	}
	return 0;
}

详情