Description
一棵树上有$n$个节点,编号分别为$1$到$n$,每个节点都有一个权值$w_i$.
有三种操作:
$1.CHANGE;u;t$:把结点$u$的权值改为$t$;
$2.QMAX;u;v$:询问从点$u$到点$v$的路径上的节点的最大权值;
$3.QSUM;u;v$:询问从点$u$到点$v$的路径上的节点的权值和.
$P.S.$ 从点$u$到点$v$的路径上的节点包括$u$和$v$本身.
Input
第$1$行,$1$个整数$n$,表示节点的个数.
接下来$n-1$行,每行$2$个整数$u$和$v$,表示节点$u$和$v$之间有一条边相连.
接下来$1$行,每行$n$个整数,第$i$个整数$w_i$.表示节点$i$的权值.
接下来$1$行,$1$个整数$q$,表示操作的总数.
接下来$q$行,每行$1$个操作,以"$CHANGE;u;t$"或者"$QMAX;u;v$"或者"$QSUM;u;v$"的形式给出.
Output
对于每个"$QMAX$”或者”$QSUM$”的操作,每行输出$1$个整数表示要求输出的结果.
Sample Input
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
Sample Output
4
1
2
2
10
6
5
6
5
16
HINT
$1;leq;n;leq;30000,0;leq;q;leq;200000$.
中途操作中保证每个节点的权值$w_iin[-30000,30000]$.
Solution
树链剖分+线段树.
不会树链剖分的,戳这->学习笔记-树链剖分
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 30005 #define M 60005 using namespace std; struct linetree{ int l,r,s,m; }lt[M]; struct graph{ int nxt,to; }e[M]; char c[10]; int g[N],w[N],ww[N],n,q,u,v,cnt; int f[N],p[N],dep[N],siz[N],son[N],top[N]; /*top[u]:u所在的链的顶端节点,son[u]:u的重儿子*/ inline void addedge(int x,int y){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y; } inline void dfs1(int u){ int m=0;siz[u]=1; for(int i=g[u];i;i=e[i].nxt) if(!dep[e[i].to]){ f[e[i].to]=u; dep[e[i].to]=dep[u]+1; dfs1(e[i].to); siz[u]+=siz[e[i].to]; if(siz[e[i].to]>m){ son[u]=e[i].to; m=siz[e[i].to]; } } } inline void dfs2(int u,int tp){ top[u]=tp;p[u]=++cnt;ww[cnt]=w[u]; if(son[u]) dfs2(son[u],tp); for(int i=g[u];i;i=e[i].nxt){ if(e[i].to!=f[u]&&e[i].to!=son[u]) dfs2(e[i].to,e[i].to); } } inline void build(int u,int l,int r){ lt[u].l=l;lt[u].r=r; if(lt[u].l<lt[u].r){ int lef=u<<1,rig=u<<1|1; int mid=(lt[u].l+lt[u].r)>>1; build(lef,l,mid);build(rig,mid+1,r); lt[u].s=lt[lef].s+lt[rig].s; lt[u].m=max(lt[lef].m,lt[rig].m); } else lt[u].s=lt[u].m=ww[lt[u].l]; } inline void cover(int u,int x,int k){ if(lt[u].l<lt[u].r){ int lef=u<<1,rig=u<<1|1; int mid=(lt[u].l+lt[u].r)>>1; if(x<=mid) cover(lef,x,k); else cover(rig,x,k); lt[u].s=lt[lef].s+lt[rig].s; lt[u].m=max(lt[lef].m,lt[rig].m); } else lt[u].s=lt[u].m=k; } inline int sum(int u,int l,int r){ if(lt[u].l>=l&<[u].r<=r) return lt[u].s; if(lt[u].l<lt[u].r){ int lef=u<<1,rig=u<<1|1,ret=0; int mid=(lt[u].l+lt[u].r)>>1; if(l<=mid) ret+=sum(lef,l,r); if(r>mid) ret+=sum(rig,l,r); return ret; } } inline int qsum(int x,int y){ int ret=0; while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]){ ret+=sum(1,p[top[x]],p[x]); x=f[top[x]]; } else{ ret+=sum(1,p[top[y]],p[y]); y=f[top[y]]; } } if(p[x]>p[y]){ int t=x;x=y;y=t; } ret+=sum(1,p[x],p[y]); return ret; } inline int ask(int u,int l,int r){ if(lt[u].l>=l&<[u].r<=r) return lt[u].m; if(lt[u].l<lt[u].r){ int lef=u<<1,rig=u<<1|1,ret=-30000; int mid=(lt[u].l+lt[u].r)>>1; if(l<=mid) ret=max(ret,ask(lef,l,r)); if(r>mid) ret=max(ret,ask(rig,l,r)); return ret; } } inline int qmax(int x,int y){ int ret=-30000; while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]){ ret=max(ret,ask(1,p[top[x]],p[x])); x=f[top[x]]; } else{ ret=max(ret,ask(1,p[top[y]],p[y])); y=f[top[y]]; } } if(p[x]>p[y]){ int t=x;x=y;y=t; } ret=max(ret,ask(1,p[x],p[y])); return ret; } inline void Aireen(){ scanf("%d",&n); for(int i=1,x,y;i<n;++i){ scanf("%d%d",&x,&y); addedge(x,y);addedge(y,x); } for(int i=1;i<=n;++i) scanf("%d",&w[i]); dep[1]=1;dfs1(1); cnt=0;dfs2(1,1); build(1,1,n); scanf("%d",&q); while(q--){ scanf("%s%d%d",c,&u,&v); if(c[1]=='H') cover(1,p[u],v); else if(c[1]=='M') printf("%d ",qmax(u,v)); else printf("%d ",qsum(u,v)); } } int main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }