题解 P4114 【Qtree1】

顾z

2018-10-20 21:10:35

Solution

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 裸的树链剖分题. 将边权转为点权要赋给深度较深的点,这样可以保证一个点权对应一个边权. 注意题目中的$a==b$的时候输出$0$,要不就一遍切了 QAQ. ``代码`` ```c++ #include<cstdio> #include<cstring> #include<iostream> #include<cctype> #define int long long #define N 100008 #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,head[N],tot; struct cod{int u,v,w,fr;}edge[N<<2]; inline void add(int x,int y,int z) { edge[++tot].u=head[x]; edge[tot].fr=x; edge[tot].v=y; edge[tot].w=z; head[x]=tot; } int son[N],size[N],f[N],depth[N],val[N]; char s[108]; void dfs1(int u,int fa,int dis) { f[u]=fa;depth[u]=depth[fa]+1;size[u]=1;val[u]=dis; for(R int i=head[u];i;i=edge[i].u) { if(edge[i].v==fa)continue; dfs1(edge[i].v,u,edge[i].w); size[u]+=size[edge[i].v]; if(son[u]==-1 or size[son[u]]<son[edge[i].v]) son[u]=edge[i].v; } } int top[N],idx,dfn[N],fdfn[N]; void dfs2(int u,int t) { top[u]=t;dfn[u]=++idx;fdfn[idx]=u; if(son[u]==-1)return; dfs2(son[u],t); for(R int i=head[u];i;i=edge[i].u) { if(dfn[edge[i].v])continue; dfs2(edge[i].v,edge[i].v); } } int tr[N<<2]; #define ls o<<1 #define rs o<<1|1 inline void up(int o){tr[o]=max(tr[ls],tr[rs]);} void build(int o,int l,int r) { if(l==r) { tr[o]=val[fdfn[l]]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); up(o); } void change(int o,int l,int r,int pos,int z) { if(l==r){tr[o]=z;return;} int mid=(l+r)>>1; if(pos<=mid)change(ls,l,mid,pos,z); else change(rs,mid+1,r,pos,z); up(o); } int query(int o,int l,int r,int x,int y) { if(x<=l and y>=r)return tr[o]; int mid=(l+r)>>1,res=-214748364766LL; if(x<=mid)res=max(res,query(ls,l,mid,x,y)); if(y>mid)res=max(res,query(rs,mid+1,r,x,y)); return res; } inline int tquery(int x,int y) { int fx=top[x],fy=top[y],res=-214748364766LL; while(fx!=fy) { if(depth[fx]>depth[fy]) { res=max(res,query(1,1,n,dfn[fx],dfn[x])); x=f[fx]; } else { res=max(res,query(1,1,n,dfn[fy],dfn[y])); y=f[fy]; } fx=top[x],fy=top[y]; } if(x==y)return res; if(dfn[x]>dfn[y])swap(x,y); res=max(res,query(1,1,n,dfn[x]+1,dfn[y])); return res; } signed main() { in(n);memset(son,-1,sizeof son); for(R int i=1,x,y,z;i<n;i++) { in(x),in(y),in(z); add(x,y,z);add(y,x,z); } dfs1(1,0,0);dfs2(1,1); build(1,1,n); for(R int x,y;;) { scanf("%s",s+1); if(s[1]=='D')break; if(s[1]=='Q') { in(x),in(y); if(x==y)puts("0"); else printf("%lld\n",tquery(x,y)); } else { in(x),in(y);x*=2; if(depth[edge[x].v]<depth[edge[x].fr]) x=edge[x].fr; else x=edge[x].v; change(1,1,n,dfn[x],y); } } } ```