1036: [ZJOI2008]树的统计Count
Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
Input
输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有 一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作 的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
Output
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
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
[这里写链接内容](http://hzwer.com/2543.html) 这题可以练一下树链剖分。 由题意得，是求树上两点的lca，lca可以用倍增表或者树剖写。 但因为要支持修改，而倍增表不支持修改，所以得用树链剖分。 修改和查询可以用线段树维护即可 本人蒟蒻，不会splay，所以这里不讲 用线段树维护最大值和总和，求出lca，时间复杂度为（N log^2） 注意这道题有负数，用了读入优化或输出优化的同学注意。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> #define N 30005 using namespace std; int n,cnt,sz; int v[N],size[N],deep[N],son[N],head[N],fa[N]; int pos[N],bl[N]; struct tre{ int l,r,mx,sum; }t[N*4]; struct edge{ int next,to; }e[N*2]; inline int read(){ int x=0,f=1;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48; return x*f; } inline void write(int x){ int a[30],f=1;a[0]=0; if(x<0) f=-1,x=-x; for(;!a[0]||x;x/=10) a[++a[0]]=x; if(f==-1) putchar('-'); for(int i=a[0];i>0;i--) putchar(a[i]+48); } inline void writeln(){ putchar('\n'); } inline void insert(int u,int v){ e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt; } inline void dfs1(int x){ size[x]=1; for(int i=head[x];i;i=e[i].next){ if(e[i].to==fa[x]) continue; fa[e[i].to]=x,deep[e[i].to]=deep[x]+1; dfs1(e[i].to); size[x]+=size[e[i].to]; } } inline void dfs2(int x,int tp){ int k=0; pos[x]=++sz;bl[x]=tp; for(int i=head[x];i;i=e[i].next) if(deep[e[i].to]>deep[x]&&size[e[i].to]>size[k]) k=e[i].to; if(!k) return; dfs2(k,tp); for(int i=head[x];i;i=e[i].next) if(e[i].to!=k&&deep[e[i].to]>deep[x]) dfs2(e[i].to,e[i].to); } inline void build(int node,int l,int r){ t[node].l=l,t[node].r=r; if(l==r) return; int mid=(l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); } inline void update(int node,int v,int val){ int l=t[node].l,r=t[node].r; if(l==r){ t[node].sum=t[node].mx=val; return; } int mid=(l+r)/2; if(v<=mid) update(node*2,v,val); else update(node*2+1,v,val); t[node].sum=t[node*2].sum+t[node*2+1].sum; t[node].mx=max(t[node*2].mx,t[node*2+1].mx); } inline int query_smax(int node,int l,int r){ if(t[node].l>=l&&t[node].r<=r) return t[node].mx; int mid=(t[node].l+t[node].r)/2; if(r<=mid) return query_smax(node*2,l,r); else if(l>mid) return query_smax(node*2+1,l,r); else return max(query_smax(node*2,l,mid),query_smax(node*2+1,mid+1,r)); } inline int query_ssum(int node,int l,int r){ if(t[node].l>=l&&t[node].r<=r) return t[node].sum; int mid=(t[node].l+t[node].r)/2; if(r<=mid) return query_ssum(node*2,l,r); else if(l>mid) return query_ssum(node*2+1,l,r); else return query_ssum(node*2,l,mid)+query_ssum(node*2+1,mid+1,r); } inline int smax(int x,int y){//lca 求最大值 int mx=-1e9; while(bl[x]!=bl[y]){ if(deep[bl[x]]<deep[bl[y]]) swap(x,y); mx=max(mx,query_smax(1,pos[bl[x]],pos[x])); x=fa[bl[x]]; } if(pos[x]>pos[y]) swap(x,y); mx=max(mx,query_smax(1,pos[x],pos[y])); return mx; } inline int ssum(int x,int y){//LCA 求和 int sum=0; while(bl[x]!=bl[y]){ if(deep[bl[x]]<deep[bl[y]]) swap(x,y); sum+=query_ssum(1,pos[bl[x]],pos[x]); x=fa[bl[x]]; } if(pos[x]>pos[y]) swap(x,y); sum+=query_ssum(1,pos[x],pos[y]); return sum; } int main(){ n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); insert(u,v); insert(v,u); } for(int i=1;i<=n;i++) v[i]=read(); dfs1(1),dfs2(1,1); build(1,1,n); for(int i=1;i<=n;i++) update(1,pos[i],v[i]); int m=read(); while(m--){ char ch[10]; scanf("%s",ch); int x=read(),y=read(); if(ch[1]=='H') v[x]=y,update(1,pos[x],y); else if(ch[1]=='M') write(smax(x,y)),writeln(); else write(ssum(x,y)),writeln(); } return 0; }orz hzwer
