用上题几乎一样的代码无压力AC嘻嘻。。。
Code：
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define pb push_back
const int inf=~0U>>1,maxn=10000;
using namespace std;
vector<int> E[maxn],Et[maxn];
int T[maxn*2],C[maxn*2],mnt;
typedef vector<int>::iterator it;
int n,w[maxn],Lim,dep[maxn],Fa[maxn],P[maxn];
int own[maxn],Max[maxn],Sum[maxn]={};
void Build(int x,int f,int d)
{
dep[x]=d;Fa[x]=f;
int t,c,tmp=own[x];
tr(e,E[x])
{
t=T[*e],c=C[*e];
if(t==f)continue;P[*e/2]=t;
w[t]=c;if(Sum[tmp]++<Lim)own[t]=tmp,Et[x].pb(t);
Build(t,x,d+1);
}
}
void Dfs(int t,int m)
{
Max[t]=m=max(m,w[t]);
tr(e,Et[t])Dfs(*e,m);
}
void Change(int t,int u)
{
w[t=P[t]]=u;
if(t==own[t])Dfs(t,-inf);
else Dfs(t,Max[Fa[t]]);
}
int QMax(int a,int b)
{
int m=-inf;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b])
m=max(m,w[a]),a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
m=max(m,Max[a]),a=Fa[own[a]];
}
}
return m;
}
void AddEdge(int s,int t,int c)
{
T[mnt]=t;C[mnt]=c;
E[s].pb(mnt);mnt++;
}
void Init()
{
scanf(" ");
scanf("%d",&n);int s,t,c;
rep(i,n)E[i].clear(),Et[i].clear();
mnt=0;w[0]=-inf;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);
–s;–t;
AddEdge(s,t,c);AddEdge(t,s,c);
}
}
void Solve()
{
Init();
Lim=sqrt(n)+1;
rep(i,n)own[i]=i,Sum[i]=1;
Build(0,-1,0);rep(i,n)if(own[i]==i)Dfs(i,-inf);
char cmd[100];int s,t;
for(;;)
{
scanf(" ");
scanf("%s",cmd);
if(cmd[0]==’D’)return;
scanf("%d%d",&s,&t);
if(cmd[0]==’Q’)printf("%dn",QMax(s-1,t-1));
else Change(s-1,t);
}
}
int main()
{
//freopen("in","r",stdin);
int t;scanf("%d",&t);
rep(i,t)Solve();
}