1036: [ZJOI2008]树的统计Count （树链剖分）-白红宇

1036: [ZJOI2008]树的统计Count （树链剖分）

阅读量：7095 次

发布时间：2019-06-28

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

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec

Memory Limit: 162 MB

Submit: 3401

Solved: 1418

[ ][ ]

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. 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

入门题

1 /* **********************************************  2 Author      : kuangbin  3 Created Time: 2013/8/12 21:58:47  4 File Name   : F:\2013ACM练习\专题学习\数链剖分\树的统计Count.cpp  5 *********************************************** */  6   7 #include 
     
        8 #include 
      
         9 #include 
       
         10 #include 
        
          11 #include 
         
           12 #include 
          
            13 #include 
           
             14 #include 
             15 #include 
             
               16 #include 
              
                17 #include 
               
                 18 using namespace std; 19 20 const int MAXN = 30010; 21 struct Edge 22 { 23 int to,next; 24 }edge[MAXN*2]; 25 int head[MAXN],tot; 26 int top[MAXN]; //top[v] 表示v所在的重链的顶端节点 27 int fa[MAXN]; //父亲节点 28 int deep[MAXN];//深度 29 int num[MAXN]; //num[v]表示以v为根的子树的节点数 30 int p[MAXN]; //p[v]表示v在线段树中的位置 31 int fp[MAXN];//和p数组相反 32 int son[MAXN];//重儿子 33 int pos; 34 void init() 35 { 36 tot = 0; 37 memset(head,-1,sizeof(head)); 38 pos = 0; 39 memset(son,-1,sizeof(son)); 40 } 41 void addedge(int u,int v) 42 { 43 edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; 44 } 45 void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son 46 { 47 deep[u] = d; 48 fa[u] = pre; 49 num[u] = 1; 50 for(int i = head[u];i != -1;i = edge[i].next) 51 { 52 int v = edge[i].to; 53 if(v != pre) 54 { 55 dfs1(v,u,d+1); 56 num[u] += num[v]; 57 if(son[u] == -1 || num[v] > num[son[u]]) 58 son[u] = v; 59 } 60 } 61 } 62 void getpos(int u,int sp) 63 { 64 top[u] = sp; 65 p[u] = pos++; 66 fp[p[u]] = u; 67 if(son[u] == -1) return; 68 getpos(son[u],sp); 69 for(int i = head[u]; i != -1 ; i = edge[i].next) 70 { 71 int v = edge[i].to; 72 if(v != son[u] && v != fa[u]) getpos(v,v); 73 } 74 } 75 76 struct Node 77 { 78 int l,r; 79 int sum; 80 int Max; 81 }segTree[MAXN*3]; 82 void push_up(int i) 83 { 84 segTree[i].sum = segTree[i<<1].sum + segTree[(i<<1)|1].sum; 85 segTree[i].Max = max(segTree[i<<1].Max,segTree[(i<<1)|1].Max); 86 } 87 int s[MAXN]; 88 void build(int i,int l,int r) 89 { 90 segTree[i].l = l; 91 segTree[i].r = r; 92 if(l == r) 93 { 94 segTree[i].sum = segTree[i].Max = s[fp[l]]; 95 return ; 96 } 97 int mid = (l + r)/2; 98 build(i<<1,l,mid); 99 build((i<<1)|1,mid+1,r);100 push_up(i);101 }102 void update(int i,int k,int val)//更新线段树的第k个值为val103 {104 if(segTree[i].l == k && segTree[i].r == k)105 {106 segTree[i].sum = segTree[i].Max = val;107 return;108 }109 int mid = (segTree[i].l + segTree[i].r)/2;110 if(k <= mid)update(i<<1,k,val);111 else update((i<<1)|1,k,val);112 push_up(i);113 }114 int queryMax(int i,int l,int r)//查询线段树[l,r]区间的最大值115 {116 if(segTree[i].l == l && segTree[i].r == r)117 {118 return segTree[i].Max;119 }120 int mid = (segTree[i].l + segTree[i].r)/2;121 if(r <= mid) return queryMax(i<<1,l,r);122 else if(l > mid)return queryMax((i<<1)|1,l,r);123 else return max(queryMax(i<<1,l,mid),queryMax((i<<1)|1,mid+1,r));124 }125 int querySum(int i,int l,int r) //查询线段树[l,r]区间的和126 {127 if(segTree[i].l == l && segTree[i].r == r)128 return segTree[i].sum;129 int mid = (segTree[i].l + segTree[i].r)/2;130 if(r <= mid)return querySum(i<<1,l,r);131 else if(l > mid)return querySum((i<<1)|1,l,r);132 else return querySum(i<<1,l,mid) + querySum((i<<1)|1,mid+1,r);133 }134 int findMax(int u,int v)//查询u->v路径上节点的最大权值135 {136 int f1 = top[u] , f2 = top[v];137 int tmp = -1000000000;138 while(f1 != f2)139 {140 if(deep[f1] < deep[f2])141 {142 swap(f1,f2);143 swap(u,v);144 }145 tmp = max(tmp,queryMax(1,p[f1],p[u]));146 u = fa[f1];147 f1 = top[u];148 }149 if(deep[u] > deep[v]) swap(u,v);150 return max(tmp,queryMax(1,p[u],p[v]));151 }152 int findSum(int u,int v) //查询u->v路径上节点的权值的和153 {154 int f1 = top[u], f2 = top[v];155 int tmp = 0;156 while(f1 != f2)157 {158 if(deep[f1] < deep[f2])159 {160 swap(f1,f2);161 swap(u,v);162 }163 tmp += querySum(1,p[f1],p[u]);164 u = fa[f1];165 f1 = top[u];166 }167 if(deep[u] > deep[v]) swap(u,v);168 return tmp + querySum(1,p[u],p[v]);169 }170 int main() 171 {172 //freopen("in.txt","r",stdin);173 //freopen("out.txt","w",stdout);174 int n;175 int q;176 char op[20];177 int u,v;178 while(scanf("%d",&n) == 1)179 {180 init();181 for(int i = 1;i < n;i++)182 {183 scanf("%d%d",&u,&v);184 addedge(u,v);185 addedge(v,u);186 }187 for(int i = 1;i <= n;i++)188 scanf("%d",&s[i]);189 dfs1(1,0,0);190 getpos(1,1);191 build(1,0,pos-1);192 scanf("%d",&q);193 while(q--)194 {195 scanf("%s%d%d",op,&u,&v);196 if(op[0] == 'C')197 update(1,p[u],v);//修改单点的值198 else if(strcmp(op,"QMAX") == 0)199 printf("%d\n",findMax(u,v));//查询u->v路径上点权的最大值200 else printf("%d\n",findSum(u,v));//查询路径上点权的和201 }202 }203 return 0;204 }

转载地址：http://kcxql.baihongyu.com/

你可能感兴趣的文章