HYSBZ 1036 树的统计Count

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1036

题意：

一棵树上有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本身

思路：

权值在点上的树链剖分+线段树单点更新+线段树成段询问。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <string>
  4 #include <cstdio>
  5 #include <vector>
  6 using namespace std;
  7 int n, q;
  8 #define maxn 30010
  9 #define lson l, m, rt<<1
 10 #define rson m+1, r, rt<<1|1
 11 int siz[maxn], top[maxn], fa[maxn], son[maxn], dep[maxn];
 12 int w[maxn], fw[maxn];
 13 int A[maxn];
 14 vector <int> mp[maxn];
 15 int pos;
 16 int sum[maxn<<2], mmax[maxn<<2];
 17 int col[maxn<<2];
 18 void PushUp(int rt)
 19 {
 20     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
 21     mmax[rt] = max(mmax[rt<<1], mmax[rt<<1|1]);
 22 }
 23 void build(int l, int r, int rt)
 24 {
 25     mmax[rt] = -0x3f3f3f3f;
 26     sum[rt] = 0;
 27     if(l == r)
 28     {
 29         mmax[rt] = A[fw[l]];
 30         sum[rt] = A[fw[l]];
 31         return;
 32     }
 33     int m = (l+r)>>1;
 34     build(lson);
 35     build(rson);
 36     PushUp(rt);
 37 }
 38 void update(int p, int val, int l, int r, int rt)
 39 {
 40     if(l == r)
 41     {
 42         sum[rt] = val; mmax[rt] = val; col[rt] = 0;
 43         return;
 44     }
 45     int m = (l+r)>>1;
 46     if(p <= m) update(p, val, lson);
 47     else update(p, val, rson);
 48     PushUp(rt);
 49 }
 50 int query_max(int L, int R, int l, int r, int rt)
 51 {
 52     if(L <= l && R >= r)
 53     {
 54         return mmax[rt];
 55     }
 56     int m = (l+r)>>1;
 57     int ret = -0x3f3f3f3f;
 58     if(L <= m) ret = max(ret, query_max(L, R, lson));
 59     if(R > m) ret = max(ret, query_max(L, R, rson));
 60     return ret;
 61 }
 62 int query_sum(int L, int R, int l, int r, int rt)
 63 {
 64     if(L <= l && R >= r)
 65     {
 66         return sum[rt];
 67     }
 68     int m = (l+r)>>1;
 69     int ret = 0;
 70     if(L <= m) ret += query_sum(L, R, lson);
 71     if(R > m) ret += query_sum(L, R, rson);
 72     return ret;
 73 }
 74 int dfs1(int u, int pre, int deep)
 75 {
 76     siz[u] = 1; dep[u] = deep; fa[u] = pre;
 77     int mmax = 0;
 78     for(int i = 0; i < mp[u].size(); i++)
 79     {
 80         if(mp[u][i] != pre)
 81         {
 82             int temp = dfs1(mp[u][i], u, deep+1);
 83             siz[u] += temp;
 84             if(son[u] == -1 || temp >= mmax) 
 85             {
 86                 son[u] = mp[u][i];
 87                 mmax = temp;
 88             }
 89         }
 90     }
 91     return siz[u];
 92 }
 93 void dfs2(int u, int val)
 94 {
 95     top[u] = val;
 96     if(son[u] != -1)
 97     {
 98         w[u] = ++pos;
 99         fw[w[u]] = u;
100         dfs2(son[u], val);
101     }
102     else if(son[u] == -1)
103     {
104         w[u] = ++pos;
105         fw[w[u]] = u;
106         return;
107     }
108     for(int i = 0; i < mp[u].size(); i++)
109     {        
110         if(mp[u][i] != son[u] && mp[u][i] != fa[u]) dfs2(mp[u][i], mp[u][i]);
111     }
112 }
113 int find_sum(int u, int v)
114 {
115     int f1 = top[u], f2 = top[v];
116     int temp = 0;
117     while(f1 != f2)
118     {
119         if(dep[f1] < dep[f2])
120         {
121             swap(f1, f2); 
122             swap(u, v);
123         }
124         temp += query_sum(w[f1], w[u], 1, pos, 1);
125         u = fa[f1]; f1 = top[u];
126     }
127     if(dep[u] > dep[v]) swap(u, v);
128     temp += query_sum(w[u], w[v], 1, pos, 1);
129     return temp;
130 }
131 int find_max(int u, int v)
132 {
133     int f1 = top[u], f2 = top[v];
134     int temp = -0x3f3f3f3f;
135     while(f1 != f2)
136     {
137         if(dep[f1] < dep[f2])
138         {
139             swap(f1, f2);
140             swap(u, v);
141         }
142         temp = max(temp, query_max(w[f1], w[u], 1, pos, 1));
143         u = fa[f1]; f1 = top[u];
144     }
145     if(dep[u] > dep[v]) swap(u, v);
146     temp = max(temp, query_max(w[u], w[v], 1, pos, 1));
147     return temp;
148 }
149 int main() 
150 {
151   //  freopen("in.txt", "r", stdin);
152    // freopen("out.txt", "w", stdout);
153     while(~scanf("%d", &n))
154     {
155         for(int i = 1; i <= n; i++) mp[i].clear(); 
156         pos = 0;
157         memset(son, -1, sizeof(son));
158         for(int i = 1; i <= n-1; i++)
159         {
160             int a, b; scanf("%d%d", &a, &b);
161             mp[a].push_back(b);
162             mp[b].push_back(a);
163         }
164         for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
165         dfs1(1, -1, 1);
166         dfs2(1, 1);
167         build(1, pos, 1);
168         
169         scanf("%d", &q);
170         char op[10];
171         while(q--)
172         {
173             scanf("%s", op); int u, v; 
174             scanf("%d%d", &u, &v);
175             if(op[0] == 'C') update(w[u], v, 1, pos, 1);
176             else if(op[1] == 'M') printf("%d
", find_max(u, v));
177             else if(op[1] == 'S') printf("%d
", find_sum(u, v));
178             
179         }
180         
181     }
182     return 0;
183 }