你不退谷了吗
by qyzyqljzzzy @ 2020-08-25 14:19:34
没有大佬看看吗..
by fzj2007 @ 2020-08-25 14:31:19
无意义回答，%%%
by hahazhou @ 2020-08-25 18:38:38
`max` 定义为宏会导致参数重复计算
@[fzj2007](/user/172370)
by andyli @ 2020-08-25 18:45:19
楼上正解
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mid (l+r>>1)
int n,head[N],dfn[N],rk[N],f[N],num,size[N],son[N],dep[N],top[N],w[N],cnt,t[N<<2];
struct edge{
int u,v,nxt,z;
}e[N<<1];
inline void add(int u,int v,int z){
e[++cnt]=(edge){u,v,head[u],z},head[u]=cnt;
}
inline void push_up(int x){
t[x]=max(t[lc(x)],t[rc(x)]);
}
inline void build(int x,int l,int r){
if(l==r) return t[x]=w[rk[l]],void();
build(lc(x),l,mid),build(rc(x),mid+1,r);
push_up(x);
}
inline void update(int x,int l,int r,int k,int val){
if(l==r) return t[x]=val,void();
if(k<=mid) update(lc(x),l,mid,k,val);
else update(rc(x),mid+1,r,k,val);
push_up(x);
}
inline int query(int x,int l,int r,int ql,int qr){
if(l>r) return 0;
if(ql<=l&&r<=qr) return t[x];
int ret=0;
if(ql<=mid) ret=max(ret,query(lc(x),l,mid,ql,qr));
if(qr>mid) ret=max(ret,query(rc(x),mid+1,r,ql,qr));
return ret;
}
void dfs1(int x,int fath){
size[x]=1,f[x]=fath,dep[x]=dep[fath]+1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fath) continue;
w[v]=e[i].z;
dfs1(v,x);
size[x]+=size[v];
if(!son[x]||size[v]>size[son[x]]) son[x]=v;
}
}
void dfs2(int x,int ct){
dfn[x]=++num,rk[num]=x,top[x]=ct;
if(son[x]) dfs2(son[x],ct);
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v!=son[x]&&v!=f[x]) dfs2(v,v);
}
}
inline void upd(int x,int val){
int u=e[x<<1].u,v=e[x<<1].v;
if(f[v]==u) swap(u,v);
update(1,1,n,dfn[u],val);
}
inline int que(int x,int y){
if(x==y) return 0;
int res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=max(res,query(1,1,n,dfn[top[x]],dfn[x]));
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
if(dfn[x] == dfn[y]) return res;
return max(res,query(1,1,n,dfn[x]+1,dfn[y]));
}
int main(){
cin>>n;
for(int i=1,u,v,z;i<n;i++)
{
cin>>u>>v>>z;add(u,v,z),add(v,u,z);
}
dfs1(1,0),dfs2(1,1),build(1,1,n);
while(1){
char ch[10];
cin>>ch;
if(ch[0]=='D') break;
int a,b;
cin>>a>>b;
if(ch[0]=='C') upd(a,b);
else cout<<que(a,b)<<endl;
}
return 0;
}
```
by JK_LOVER @ 2020-08-25 18:47:13
@[andyli](/user/84282) 哦感谢%%
by fzj2007 @ 2020-08-25 19:11:41