蒟蒻求调（re on#1）

#include<bits/stdc++.h>
#define N 1000005
#define lson u<<1
#define rson (u<<1)|1
using namespace std;
typedef pair<int,int> pii;
int n,vistime=0;
int a[N],d[N],dfn[N],rdfn[N],fa[N],wc[N],siz[N],top[N];
struct road{
	int u,v;
}ro[N];
vector<pii> e[N];
void dfs1(int,int);
void dfs2(int,int);

struct node{
	int l,r;
	int maxn;
}tr[N*4];
void build(int,int,int);
inline void pushup(int);
void modify(int,int,int);
int query_link(int,int);
int query(int,int,int);


signed main()
{
	cin>>n;
	for(int i=1,u,v,c;i<=n;i++)
	{
		scanf("%d%d%d",&u,&v,&c);
		ro[i]={u,v};
		e[u].push_back({v,c});
		e[v].push_back({u,c});
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	char s[10];
	int x,y;
//	cout<<vistime<<endl<<endl;
	while(scanf("%s",(s+1))!=EOF)
	{
		if(s[1]=='D') break;
		scanf("%d%d",&x,&y);
		if(s[1]=='C')
		{
			int u=ro[x].u,v=ro[x].v;
			x=d[u]>d[v]?u:v;
			modify(1,dfn[x],y);
		}
		else if(s[1]=='Q')
		{
			if(x==y){
				printf("0\n");
				continue;
			}
			printf("%d\n",query_link(x,y));
		}
	}
	return 0;
}

void dfs1(int x,int father)
{
	siz[x]=1;
	fa[x]=father;
	d[x]=d[father]+1;
	for(int i=0;i<(int)e[x].size();i++)
	{
		int y=e[x][i].first,c=e[x][i].second;
		if(y==fa[x]) continue;
		a[y]=c;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[wc[x]]) wc[x]=y;
	}
}

void dfs2(int x,int TOP)
{
//	if(dfn[x]) return; 没有这行会重复遍历
	dfn[x]=++vistime;
	rdfn[vistime]=x;
	top[x]=TOP;
	if(wc[x])
	{
		dfs2(wc[x],TOP);
		for(int i=0;i<(int)e[x].size();i++)
		{
			int y=e[x][i].first;
			if(y==fa[x]||y==wc[x]) continue;
			dfs2(y,y);
		}
	}
}

void build(int u,int l,int r)
{
	tr[u]={l,r};
	if(l==r)
	{
		tr[u].maxn=a[rdfn[l]];
		return;
	}
	int mid=(l+r)/2;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(u);
}

inline void pushup(int u)
{
	tr[u].maxn=max(tr[lson].maxn,tr[rson].maxn);
}

void modify(int u,int pos,int c)
{
	if(tr[u].l==tr[u].r)
	{
		tr[u].maxn=c;
		return;
	}
	int mid=(tr[u].l+tr[u].r)/2;
	if(pos<=mid) modify(lson,pos,c);
	else modify(rson,pos,c);
	pushup(u);
}

int query(int u,int l,int r)
{
	if(l>r) return 0;
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].maxn;
	int mid=(tr[u].l+tr[u].r)/2;
	int ans=0;
	if(l<=mid) ans=max(ans,query(lson,l,r));
	if(r>mid) ans=max(ans,query(rson,l,r));
	return ans;
}

int query_link(int u,int v)
{
	int ans=0;
	while(top[u]!=top[v])
	{
		if(d[top[v]]>d[top[u]]) swap(u,v);
		ans=max(ans,query(1,dfn[top[u]],dfn[u]));
		u=fa[top[u]];
	}
	if(dfn[u]==dfn[v]) return ans;
	return max(ans,query(1,min(dfn[u],dfn[v])+1,max(dfn[u],dfn[v])));
}