题解 P4114 【Qtree1】

~~这不就是个树剖裸题么~~ 树剖一下，然后用线段树维护区间最大值 每次是单点修改 这道题的难点在于边权怎么处理 我们可以在两点连的边之间新建一个节点，把边的权值赋给它，对于原树上的节点为了不影响赋成-inf 然后这题就做完了 ```cpp #include<iostream> #include<cstdio> #define mid ((l+r)>>1) #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ls k<<1 #define rs k<<1|1 using namespace std; const int N=100005,inf=1e9; int n,cnt,tot; int head[N<<1],siz[N<<1],top[N<<1],fa[N<<1],dep[N<<1],son[N<<1],id[N<<1],vl[N<<1],val[N<<1]; int tr[N<<3]; struct node{ int to,nxt; }e[N<<2]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } inline void add(int from,int to){ e[++cnt]=(node){to,head[from]}; head[from]=cnt; } void dfs1(int x,int f,int deep){ fa[x]=f;siz[x]=1;dep[x]=deep; int maxson=-1; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f){ dfs1(e[i].to,x,deep+1); siz[x]+=siz[e[i].to]; if(siz[e[i].to]>maxson)son[x]=e[i].to,maxson=siz[e[i].to]; } } void dfs2(int x,int topf){ id[x]=++tot;val[tot]=vl[x];top[x]=topf; if(!son[x])return ; dfs2(son[x],topf); for(int i=head[x];i;i=e[i].nxt){ if(e[i].to==fa[x]||e[i].to==son[x])continue; dfs2(e[i].to,e[i].to); } } inline void update(int k){ tr[k]=max(tr[ls],tr[rs]); } void change(int k,int l,int r,int x,int y){ if(l==r&&l==x){ tr[k]=y; return ; } if(x<=mid)change(lson,x,y); else change(rson,x,y); update(k); } int ask(int k,int l,int r,int x,int y){ if(l==x&&y==r){ return tr[k]; } if(y<=mid)return ask(lson,x,y); else if(x>mid)return ask(rson,x,y); else return max(ask(lson,x,mid),ask(rson,mid+1,y)); } void build(int k,int l,int r){ if(l==r){ tr[k]=val[l]; return ; } build(lson);build(rson); update(k); } int query(int x,int y){ if(x==y)return 0; int ans=-inf; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])x^=y^=x^=y; ans=max(ask(1,1,(n<<1)-1,id[top[x]],id[x]),ans); x=fa[top[x]]; } if(dep[x]<dep[y])x^=y^=x^=y; ans=max(ans,ask(1,1,(n<<1)-1,id[y],id[x])); return ans; } int main(){ n=read(); int x,y; for(int i=1;i<n;++i){ x=read();y=read(); add(x,i+n);add(i+n,x); add(y,i+n);add(i+n,y); vl[i+n]=read();vl[x]=vl[y]=-inf; } dfs1(1,0,1); dfs2(1,1); build(1,1,(n<<1)-1); char c[10]; while(1){ scanf("%s",c+1); if(c[1]=='D')return 0; x=read();y=read(); if(c[1]=='Q')printf("%d\n",query(x,y)); else change(1,1,(n<<1)-1,id[x+n],y); } } ```