rt，洛谷绑定了账号提交还是waiting，去官网交的

#include <iostream>
#include <cstring>
using namespace std;
const int kMaxN=1e4+1;
struct SPLF
{
  int size,deep,father,heavyson,top,newid;
}s[kMaxN*2];
struct XDS
{
  int l,r;
  int val,tag;
}tr[kMaxN*4];
int ti,n;
struct EDGE
{
  int to,nt,dis;
}e[kMaxN*2];
int hd[kMaxN],cnt,num;
int f[kMaxN],t[kMaxN];
int a[kMaxN],b[kMaxN];
void Build(int where,int l,int r)
{
  tr[where].l=l;
  tr[where].r=r;
  tr[where].tag=1e9;
  if(l==r)
  {
    tr[where].val=b[l];
    return;
  }
  int mid=(l+r)/2;
  Build(where*2,l,mid);
  Build(where*2+1,mid+1,r);
  tr[where].val=max(tr[where*2].val,tr[where*2+1].val);
}
void Update(int where,int l,int r,int k)
{
  if(tr[where].l>=l&&tr[where].r<=r)
  {
    tr[where].val=k;
    return;
  }
  int mid=(tr[where].l+tr[where].r)/2;
  if(mid>=l)
  {
    Update(where*2,l,r,k);
  }
  if(mid<r)
  {
    Update(where*2+1,l,r,k);
  }
  tr[where].val=max(tr[where*2].val,tr[where*2+1].val);
}
int Get_Max(int where,int l,int r)
{
  if(tr[where].l>=l&&tr[where].r<=r)
  {
    return tr[where].val;
  }
  int mid=(tr[where].l+tr[where].r)/2,ans=0;
  if(mid>=l)
  {
    ans=max(ans,Get_Max(where*2,l,r));
  }
  if(mid<r)
  {
    ans=max(ans,Get_Max(where*2+1,l,r));
  }
  tr[where].val=max(tr[where*2].val,tr[where*2+1].val);
  return ans;
}
void Add(int a,int b,int c)
{
  e[++cnt].to=b;
  e[cnt].nt=hd[a];
  hd[a]=cnt;
  e[cnt].dis=c;
}
void dfs1(int now,int last)
{
  s[now].father=last;
  s[now].deep=s[last].deep+1;
  s[now].size=1;
  int maxa=-1;
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==last)continue;
    a[e[i].to]=e[i].dis;
    dfs1(e[i].to,now);
    s[now].size+=s[e[i].to].size;
    if(s[e[i].to].size>maxa)
    {
      maxa=s[e[i].to].size;
      s[now].heavyson=e[i].to;
    }
  }
}
void dfs2(int now,int top)
{
  s[now].top=top;
  s[now].newid=++num;
  b[num]=a[now];
  if(!s[now].heavyson)return;
  dfs2(s[now].heavyson,top);
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==s[now].father||e[i].to==s[now].heavyson)continue;
    dfs2(e[i].to,e[i].to);
  }
}
int Get(int x,int y)
{
  int ans=0;
  while(s[x].top!=s[y].top)
  {
    if(s[s[x].top].deep<s[s[y].top].deep)
    {
      swap(x,y);
    }
    ans=max(ans,Get_Max(1,s[s[x].top].newid,s[x].newid));
  }
  if(s[x].deep>s[y].deep)
  {
    swap(x,y);
  }
  ans=max(ans,Get_Max(1,s[x].newid+1,s[y].newid));
  return ans;
}
signed main()
{
cin>>ti;
while(ti--)
{
  cin>>n;
  cnt=0;
  memset(e,0,sizeof(e));
  memset(s,0,sizeof(s));
  memset(tr,0,sizeof(tr));
  memset(hd,0,sizeof(hd));
  for(int i=1;i<n;i++)
  {
    int c;
    cin>>f[i]>>t[i]>>c;
    Add(f[i],t[i],c);
    Add(t[i],f[i],c);
  }
  dfs1(1,0);
  dfs2(1,1);
  Build(1,1,n);
  string op;
  while(cin>>op)
  {
    if(op=="DONE")break;
    int x,y;
    cin>>x>>y;
    if(op=="CHANGE")
    {
      int where;
      if(s[f[x]].deep>s[t[x]].deep)where=s[f[x]].newid;
      else where=s[t[x]].newid;
      Update(1,where,where,y);
    }
    else
    {
      cout<<Get(x,y)<<"\n";
    }
  }
}
return 0;
}