【BZOJ1036】树的统计-白红宇

【BZOJ1036】树的统计

阅读量：5335 次

发布时间：2019-06-15

本文共 3463 字，大约阅读时间需要 11 分钟。

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 18285 Solved: 7445

[][][]

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

1 2

2 3

4 1

4 2 1 3

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

题解：树链剖分模板题，不解释啦。

树链剖分详见大佬们的博客，介绍得很详细

http://hzwer.com/2543.html

http://www.cnblogs.com/ghostfly233/p/7168324.html

代码如下：

1 #include
      
         2 #include
       
          3 #include
        
           4 #define Max 30005  5 #define INF 0x7fffffff  6 using namespace std;  7 int n,m,cnt,v[Max],dep[Max],size[Max],fa[Max];  8 int pos[Max],center[Max];//pos:节点标号 center:节点所在重链链头   9 vector
         
           G[Max]; 10 struct node{
    int l,r,sum,maxn;}tree[3*Max]; 11 void init(){ 12     scanf("%d",&n); 13     for(int i=1;i
          
           dep[x]&&size[to]>size[k]) k=to;//找出重儿子  34     } 35     if(k==0) return; 36     dfs2(k,chain);//重儿子继承重链  37     for(int i=0;i
           
            dep[x]&&k!=to) dfs2(to,to);//其余儿子分别重新开链 40 } 41 } 42 void build(int k,int l,int r){ //建线段树 43 tree[k].l=l; tree[k].r=r; 44 if(l==r) return; 45 int mid=(l+r)>>1; 46 build(k<<1,l,mid); build(k<<1|1,mid+1,r); 47 } 48 void change(int k,int x,int add){ //单点修改 49 int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1; 50 if(l==r){tree[k].sum=tree[k].maxn=add; return;} 51 if(x<=mid) change(k<<1,x,add); 52 else change(k<<1|1,x,add); 53 tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; 54 tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn); 55 } 56 int querymaxn(int k,int x,int y){ 57 int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1; 58 if(l==x&&r==y) return tree[k].maxn; 59 if(y<=mid) return querymaxn(k<<1,x,y); 60 else if(x>mid) return querymaxn(k<<1|1,x,y); 61 else return max(querymaxn(k<<1,x,mid),querymaxn(k<<1|1,mid+1,y)); 62 } 63 int querysum(int k,int x,int y){ 64 int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1; 65 if(l==x&&r==y) return tree[k].sum; 66 if(y<=mid) return querysum(k<<1,x,y); 67 else if(x>mid) return querysum(k<<1|1,x,y); 68 else return querysum(k<<1,x,mid)+querysum(k<<1|1,mid+1,y); 69 } 70 int solvemaxn(int x,int y){ 71 int ret=-INF; 72 while(center[x]!=center[y]){ //不在同一重链 73 if(dep[center[x]]
            
             pos[y]) swap(x,y);//走到同一重链后还要在查询两点间这一段 78 ret=max(ret,querymaxn(1,pos[x],pos[y])); 79 return ret; 80 } 81 int solvesum(int x,int y){ 82 int ret=0; 83 while(center[x]!=center[y]){ 84 if(dep[center[x]]
             
              pos[y]) swap(x,y); 89 ret+=querysum(1,pos[x],pos[y]); 90 return ret; 91 } 92 void solve(){ 93 build(1,1,n); 94 for(int i=1;i<=n;i++) change(1,pos[i],v[i]); 95 scanf("%d",&m); 96 for(int i=1;i<=m;i++){ 97 int x,y; char ch[10]; 98 scanf("%s%d%d",ch,&x,&y); 99 if(ch[0]=='C') change(1,pos[x],y);100 else if(ch[1]=='M') printf("%d\n",solvemaxn(x,y));101 else printf("%d\n",solvesum(x,y));102 }103 }104 int main()105 {106 init();107 dfs1(1);108 dfs2(1,1);109 solve();110 return 0;111 }