\u7528\u4e0a\u9898\u51e0\u4e4e\u4e00\u6837\u7684\u4ee3\u7801\u65e0\u538b\u529bAC\u563b\u563b\u3002\u3002\u3002
Code\uff1a
#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();
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u7528\u4e0a\u9898\u51e0\u4e4e\u4e00\u6837\u7684\u4ee3\u7801\u65e0\u538b\u529bAC\u563b\u563b\u3002\u3002\u3002Code\uff1a#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_backconst 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/300"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=300"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/300\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=300"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=300"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=300"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}