@[大帅哥就是ME](/space/show?uid=60072) 我要%您啊，机房巨神
by kl膜法59改 @ 2018-11-01 19:11:00
太NB了，我加之前所有点RE，加了之后就AC了
by tuo3288 @ 2019-01-22 22:33:05
我这为啥RE啊
```
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=(1e5)*4+5;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
struct EDGE{
int to,next,v;
}edge[N];
int head[N],tot=0,w[N],n,q;
int dep[N],top[N],seg[N],rev[M],size[N],son[N],U[N],V[N];
int Sum,maxn;
int sum[M],num[N],father[N],MAX[N];
void insert(int x,int y,int w)
{
tot++;
edge[tot].to=y;
edge[tot].v=w;
edge[tot].next=head[x];
head[x]=tot;
}
/*----------------------------------
———— fly_仙
-----------------------------------*/
void dfs1(int u,int f)
{
size[u]=1;
father[u]=f;
dep[u]=dep[f]+1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v!=f)
{
num[v]=edge[i].v;
dfs1(v,u);
size[u]+=size[v];//往回传儿子的子节点数；
if(size[v]>size[son[u]]) son[u]=v;//找到重儿子
}
}
}
void dfs2(int u,int f)
{
if(son[u])//有重儿子（不是根节点）（待确认）
{
seg[son[u]]=++seg[0];//seg[0]就是一个计数的sum， seg【】记录的是它对应树的下标
rev[seg[0]]=son[u];//rev【】记录的是树下标对应的我原本的编号
top[son[u]]=top[u];//所在重路径最小层（顶部节点）
dfs2(son[u],u);
} //整个是先可一条重路径来（待确认）
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!top[v])//没访问过
{
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,u);
}
}
}
void build(int k,int l,int r)
{
int mid=l+r>>1;
if(l==r)
{
MAX[k]=num[rev[l]];//跟正常建树一样赋初值
return;
}
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
MAX[k]=max(MAX[k<<1],MAX[k<<1|1]);
}
void query_max(int k,int l,int r,int L,int R)
{
if(L>r||R<l) return;
if(L<=l&&r<=R)
{
maxn=max(maxn,MAX[k]);
return;
}
int mid=l+r>>1;
if(mid>=L) query_max(k<<1,l,mid,L,R);
if(mid+1<=R) query_max(k<<1|1,mid+1,r,L,R);
}
void change(int k,int l,int r,int V,int pos)
{
if(pos>r||pos<l) return;
if(l==r&&r==pos)
{
MAX[k]=V;
return;
}
int mid=l+r>>1;
if(mid>=pos) change(k<<1,l,mid,V,pos);
if(mid+1<=pos) change(k<<1|1,mid+1,r,V,pos);
MAX[k]=max(MAX[k<<1],MAX[k<<1|1]);
}
void ask(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
query_max(1,1,seg[0],seg[fx],seg[x]);
x=father[fx];fx=top[x];
}
if(seg[x]>seg[y]) swap(x,y);
query_max(1,1,seg[0],seg[x]+1,seg[y]); //因为dfs序保证 在一条重链上dfs序是从浅到深逐渐增加的
// 而lca在寻求过程中，最浅的保留的是f【Ta】和Ta的路径不在查询范围内所以加一就好
}
int main()
{
memset(head,-1,sizeof(head));
int x,y,w;
n=read();
for(int i=1;i<=n-1;i++)
{
x=read(),y=read(),w=read();
insert(x,y,w);
insert(y,x,w);
U[i]=x,V[i]=y;
}
dfs1(1,0);
seg[0]=seg[1]=top[1]=rev[1]=1;//以1开始
dfs2(1,0);
build(1,1,seg[0]);
char s[10];
while(1)
{
scanf("%s",s);
if(s[0]=='D') break;
x=read(),y=read();
if(s[0]=='Q')
{
if(x==y) printf("0\n");
else {
maxn=0;
ask(x,y);
printf("%d\n",maxn);
}}
if(s[0]=='C')
{
int u=U[x],v=V[x];
if(u==father[v]) swap(u,v);
change(1,1,seg[0],y,seg[u]);
}
}
return 0;
}
```
by fly仙 @ 2019-08-09 22:28:58