求出C语言

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define max(x,y) (x>y?x:y)
#define swap(x,y) (x^=y^=x^=y)
const int INF=INT_MAX;
const int N=1e4+10,M=1e4+10;
int n;
struct edge{int x,y,c,pre;}a[M*2];
int alen,last[N];
void ins(int x,int y,int c) {alen++;a[alen].x=x,a[alen].y=y,a[alen].c=c,a[alen].pre=last[x];last[x]=alen;}
struct tnode{
	int fa,dep,son,siz,tp,id;
}t[N];
int pos[N],num[N],w[N],cnt;
void dfs1(int x,int fa)
{
	t[x].fa=fa;t[x].dep=t[fa].dep+1;t[x].son=0;
	t[x].siz=1;t[x].tp=0;t[x].id=0;
	for(int k=last[x];k;k=a[k].pre)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			num[(k+1)/2]=y;
			w[y]=a[k].c;
			dfs1(y,x);
			t[x].siz+=t[y].siz;
			if(t[t[x].son].siz<t[y].siz) t[x].son=y;
		}
	}
}
void dfs2(int x,int tp)
{
	t[x].tp=tp;
	t[x].id=++cnt;pos[cnt]=x;
	if(t[x].son) dfs2(t[x].son,tp);
	for(int k=last[x];k;k=a[k].pre)
	{
		int y=a[k].y;
		if(y!=t[x].fa&&y!=t[x].son) dfs2(y,y);
	}
}
struct trnode{
	int l,r,lc,rc,c;
}tr[N*4];
int trlen;
void push_up(int now,int lc,int rc) {tr[now].c=max(tr[lc].c,tr[rc].c);}
void build_tree(int l,int r)
{
	int now=++trlen;
	tr[now].l=l,tr[now].r=r,tr[now].lc=-1,tr[now].rc=-1,tr[now].c=-INF;
	if(l==r) tr[now].c=w[pos[l]];
	else
	{
		int mid=(l+r)/2;
		tr[now].lc=trlen+1;build_tree(l,mid);
		tr[now].rc=trlen+1;build_tree(mid+1,r);
		push_up(now,tr[now].lc,tr[now].rc);
	}
}
void modify(int now,int x,int c)
{
	if(tr[now].l==tr[now].r) {tr[now].c=c;return;}
	int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
	if(x<=mid) modify(lc,x,c);
	else modify(rc,x,c);
	push_up(now,lc,rc);
}
int query(int now,int l,int r)
{
	if(l>r||!l||!r) return -INF;
	if(tr[now].l==l&&tr[now].r==r) return tr[now].c;
	int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
	if(r<=mid) return query(lc,l,r);
	else if(l>=mid+1) return query(rc,l,r);
	else return max(query(lc,l,mid),query(rc,mid+1,r));
}
int Query(int x,int y)
{
	int res=-INF;
	while(t[x].tp!=t[y].tp)
	{
		if(t[t[x].tp].dep<t[t[y].tp].dep) swap(x,y);
		res=max(res,query(1,t[t[x].tp].id,t[x].id));
		x=t[t[x].tp].fa;
	}
	if(t[x].dep>t[y].dep) swap(x,y);
	res=max(res,query(1,t[t[x].son].id,t[y].id));
	return res;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		alen=0;memset(last,0,sizeof(last));
		for(int i=1;i<=n;i++)
		{
			int x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			ins(x,y,c),ins(y,x,c);
		}
		cnt=0;dfs1(1,0),dfs2(1,1);
		trlen=0;build_tree(1,cnt);
		char s[10];
		while(scanf("%s",s)!=EOF&&s[0]!='D')
		{
			int x,y,c;
			if(s[0]=='Q')
			{
				scanf("%d%d",&x,&y);
				printf("%d\n",Query(x,y));
			}
			else
			{
				scanf("%d%d",&x,&c);
				modify(1,t[num[x]].id,c);
			}
		}
	}
	return 0;
}