@[powerfire](/space/show?uid=152323)
树状数组，信我的没错。
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define int LL
#define lowbit(i) ((i)&(-(i)))
using namespace std;
typedef long long LL;
const int MAX_N=100005;
int n,m;
vector <int> g[MAX_N];
int bel[MAX_N];
int siz[MAX_N];
int depth[MAX_N];
int W[MAX_N];
int sum[MAX_N];
int dfn[MAX_N];
int Index;
int f[MAX_N][21];
int A[MAX_N];
int to[MAX_N];
pair<int,int> edge[MAX_N];
int dfs_(int v,int fa)
{
f[v][0]=fa;
depth[v]=depth[fa]+1;
siz[v]=1;
for(int i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(u==fa)continue;
siz[v]+=dfs_(u,v);
}
return siz[v];
}
void dfs(int v,int chain)
{
dfn[v]=++Index;
bel[v]=chain;
int k=0;
for(int i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(depth[u]==depth[v]+1 && siz[u]>siz[k])k=u;
}
if(k)dfs(k,chain);
for(int i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(depth[u]==depth[v]+1 && u!=k)dfs(u,u);
}
}
struct BIT
{
int bit[MAX_N];
void init()
{
memset(bit,0,sizeof(bit));
}
void modify(int i,int x)
{
A[i]=x;
while(i<=n)
{
bit[i]=A[i];
for(int j=1;j<lowbit(i);j<<=1)
{
bit[i]=max(bit[i],bit[i-j]);
}
i+=lowbit(i);
}
}
int query(int l,int r)
{
if(r<l)return 0;
int ans=A[r];
while(true)
{
ans=max(ans,A[r]);
if(r<=l) break;
r--;
while(r-l>=lowbit(r))
{
ans=max(ans,bit[r]);
r-=lowbit(r);
}
}
return ans;
}
}bit;
int lca(int u,int v)
{
if(depth[u]<depth[v])swap(u,v);
int t=depth[u]-depth[v];
for(int j=20;j>=0;j--)
{
if(t&(1<<j))u=f[u][j];
}
if(u==v)return v;
for(int j=20;j>=0;j--)
{
if(f[u][j]!=f[v][j])
{
u=f[u][j];
v=f[v][j];
}
}
return f[u][0];
}
int read()
{
char ch=' ';
int x=0;
bool flag=false;
while(!isdigit(ch))
{
if(ch=='-')flag=true;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return flag?-x:x;
}
signed main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
edge[i]=make_pair(u,v);
g[u].push_back(v);
g[v].push_back(u);
W[i]=read();
}
dfs_(1,0);
dfs(1,1);
for(int i=1;i<n;i++)
{
int u,v;
u=edge[i].first;
v=edge[i].second;
if(depth[u]<depth[v])swap(u,v);
bit.modify(dfn[u],W[i]);
to[i]=u;
}
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
while(true)
{
string opt;
cin>>opt;
if(opt=="CHANGE")
{
int u=read(),w=read();
bit.modify(dfn[to[u]],w);
}
else if(opt=="QUERY")
{
int u=read(),v=read();
int t=lca(u,v);
int ans=0;
while(bel[u]!=bel[t])
{
ans=max(ans,bit.query(dfn[bel[u]],dfn[u]));
u=f[bel[u]][0];
}
ans=max(ans,bit.query(dfn[t]+1,dfn[u]));
while(bel[v]!=bel[t])
{
ans=max(ans,bit.query(dfn[bel[v]],dfn[v]));
v=f[bel[v]][0];
}
ans=max(ans,bit.query(dfn[t]+1,dfn[v]));
printf("%lld\n",ans);
}
else break;
}
return 0;
}
```
by Smile_Cindy @ 2019-03-03 15:35:24