1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 18717 Solved: 7640
[Submit][Status][Discuss]
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
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
1
2
2
10
6
5
6
5
16
题解
树链剖分模板题
#include<cstdio> #include<algorithm> #include<cstring> #define maxn 30005 #define lson o<<1,l,m #define rson o<<1|1,m+1,r #define inf 1<<29 using namespace std; int data[maxn],n,sum[maxn<<2],maxx[maxn<<2],tree[maxn],siz[maxn],head[maxn],deep[maxn],son[maxn],pre[maxn]; int ecnt,fa[maxn],ord,top[maxn]; struct edge{ int u,v,next; }E[maxn*2]; void add(int u,int v) { E[++ecnt].u=u; E[ecnt].v=v; E[ecnt].next=head[u]; head[u]=ecnt; } void pushup(int o) { sum[o]=sum[o<<1]+sum[o<<1|1]; maxx[o]=max(maxx[o<<1],maxx[o<<1|1]); } void dfs(int num) { siz[num]=1; for(int i=head[num] ; i ; i=E[i].next ) { int v=E[i].v; if(fa[num]==v)continue; fa[v]=num; deep[v]=deep[num]+1; dfs(v); siz[num]+=siz[v]; if(siz[son[num]]<siz[v])son[num]=v; } } void dfs2(int num,int tp) { tree[num]=++ord;top[num]=tp;pre[tree[num]]=num; if(son[num])dfs2(son[num],tp); for(int i=head[num] ; i ; i=E[i].next ) { int v=E[i].v; if(son[num]==v||fa[num]==v)continue; dfs2(v,v); } } void build(int o,int l,int r) { if(l==r) { sum[o]=maxx[o]=data[pre[l]]; return ; } int m=(l+r)>>1; build(lson);build(rson); pushup(o); return ; } void update(int o,int l,int r,int x,int val) { if(l==r) { sum[o]=val; maxx[o]=val; return ; } int m=(l+r)>>1; if(x<=m)update(lson,x,val); else update(rson,x,val); pushup(o); return ; } int query_max(int o,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { return maxx[o]; } int ret=-inf; int m=(l+r)>>1; if(ql<=m)ret=max(ret,query_max(lson,ql,qr)); if(qr>m)ret=max(ret,query_max(rson,ql,qr)); return ret; } int que_max(int x,int y) { int fx=top[x],fy=top[y]; int ans=-inf; while(fx!=fy) { if(deep[fx]<deep[fy]){swap(fx,fy);swap(x,y);} ans=max(ans,query_max(1,1,n,tree[fx],tree[x])); x=fa[fx];fx=top[x]; } if(deep[x]>deep[y]){swap(x,y);} ans=max(ans,query_max(1,1,n,tree[x],tree[y])); return ans; } int query_sum(int o,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { return sum[o]; } int ret(0); int m=(l+r)>>1; if(ql<=m)ret+=query_sum(lson,ql,qr); if(qr>m)ret+=query_sum(rson,ql,qr); return ret; } int que_sum(int x,int y) { int ret(0); int fx=top[x],fy=top[y]; while(fx!=fy) { if(deep[fx]<deep[fy]) { swap(fx,fy);swap(x,y); } ret+=query_sum(1,1,n,tree[fx],tree[x]); x=fa[fx];fx=top[x]; } if(deep[y]<deep[x])swap(x,y); ret+=query_sum(1,1,n,tree[x],tree[y]); return ret; } int main() { int a,b,q; char str[10]; scanf("%d",&n); for(int i=1 ; i<n ; ++i ) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } for(int i=1 ; i<=n ; ++i ) { scanf("%d",&data[i]); } dfs(1);dfs2(1,1);build(1,1,n); scanf("%d",&q); while(q--) { scanf("%s",str); scanf("%d%d",&a,&b); if(str[0]=='C') { update(1,1,n,tree[a],b); data[a]=b; } if(str[1]=='M') { printf("%d ",que_max(a,b)); } if(str[1]=='S') { printf("%d ",que_sum(a,b)); } } return 0; }