C++ 解法, 执行用时: 466ms, 内存消耗: 60972K, 提交时间: 2022-06-03 15:28:10

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
using pp=pair<int,int>;
int n,k,m,x,y,tot,ans,dep[N],a[N],d[N],lg[N],mi[N][20];
pp f[N][20];
vector<int>p[N];
struct dd
{
	int x,y,z;
	friend bool operator <(dd a,dd b)
	{
		return a.z<b.z;
	}
}q[N];
void dg(int x,int y)
{
	a[++tot]=x;
	d[x]=tot;
	dep[x]=dep[y]+1;
	for (auto t:p[x])
	if (t^y)
	{
		dg(t,x);
		a[++tot]=x;
	} 
}
int lca(int x,int y)
{
    if (d[x]>d[y]) swap(x,y);
    int k=lg[d[y]-d[x]+1];
    if (dep[mi[d[x]][k]]<dep[mi[d[y]-(1<<k)+1][k]]) return mi[d[x]][k];
    else return mi[d[y]-(1<<k)+1][k];
}
pp get(pp a,pp b)
{
	if (a==(pp){1e9,1e9}) return b; 
	if (a==(pp){-1,-1} || b==(pp){-1,-1}) return {-1,-1};
	int x[4];
	x[0]=lca(a.first,b.first);
	x[1]=lca(a.first,b.second);
	x[2]=lca(a.second,b.first);
	x[3]=lca(a.second,b.second);
	sort(x,x+4,[&](int a,int b){return dep[a]<dep[b];});
	if (x[2]^x[3]) return {x[2],x[3]};
	int p=lca(a.first,a.second);
	int q=lca(b.first,b.second);
	if (dep[x[2]]>=max(dep[p],dep[q])) return {x[2],x[2]};
	return {-1,-1};
}
bool in(int x,pp a)
{
	int z=lca(a.first,a.second);
	if (lca(x,z)!=z) return 0;
	return lca(x,a.first)==x || lca(x,a.second)==x;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k>>m;
	for (int i=1;i<n;i++)
	{
		cin>>x>>y;
		p[x].emplace_back(y);
		p[y].emplace_back(x);
	}
	dg(1,0);
	lg[0]=-1;
	for (int i=1;i<=tot;i++) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=tot;i++) mi[i][0]=a[i];
	for (int j=1;j<18;j++)
		for (int i=1;i<=tot-(1<<j)+1;i++)
		mi[i][j]=dep[mi[i][j-1]]<dep[mi[i+(1<<j-1)][j-1]]?mi[i][j-1]:mi[i+(1<<j-1)][j-1];
	for (int i=1;i<=k;i++) cin>>q[i].x>>q[i].y>>q[i].z;
	sort(q+1,q+k+1);
	for (int i=1;i<=k;i++) f[i][0]={q[i].x,q[i].y};
	for (int j=1;j<18;j++)
		for (int i=1;i<=k-(1<<j)+1;i++)
		f[i][j]=get(f[i][j-1],f[i+(1<<j-1)][j-1]);
	int le=1;
	while (m--)
	{
		int tp;
		cin>>tp;
		if (tp==0) le++;
		else
		{
			cin>>x;
			x^=ans;
			pp w={1e9,1e9};
			int pos=le;
			for (int j=17;j>=0;j--)
			if (pos+(1<<j)-1<=k)
			{
				pp t=get(w,f[pos][j]);
				if (t!=(pp){-1,-1} && in(x,t))
				{
					w=t;
					pos+=1<<j; 
				}
			}
			if (pos<=k) ans=q[pos].z; else ans=-1; 
			cout<<ans<<'\n';
		}
	}
	return 0;
}