树的统计Count(树链剖分入门)

描述

传送门:BZOJ1036

一棵树上有$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$行的整数$w_i$表示节点$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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
2
3
4
5
6
7
8
9
10
4
1
2
2
10
6
5
6
5
16

思路

学习的博客:树链剖分原理和实现
树链剖分的入门题,将树分割成多条链,然后利用数据结构(这题用线段树)来维护这些链。
注意线段树的初始化……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1 << 15;
struct HLD
{
int n, dfs_clock;
int sz[maxn], top[maxn], son[maxn], dep[maxn], fa[maxn], id[maxn], val[maxn];
vector<int> G[maxn];
void init(int n)
{
this->n = n, clr(son, -1), dfs_clock = 0;
for (int i = 0; i <= n; i++) G[i].clear();
}
void add_edge(int u, int v) { G[u].pb(v), G[v].pb(u); }
void dfs(int u, int p, int d)
{
dep[u] = d, fa[u] = p, sz[u] = 1;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (v == p) continue;
dfs(v, u, d + 1);
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void link(int u, int t)
{
top[u] = t, id[u] = ++dfs_clock;
if (son[u] == -1) return;
link(son[u], t);
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (v != son[u] && v != fa[u]) link(v, v);
}
}
void getval()
{
for (int i = 1; i <= n; i++) scanf("%d", &val[id[i]]);
}
void update(int u, int v) { update(id[u], v, 1, n); }
int query_max(int u, int v)
{
int ret = -INF;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = max(ret, query_max(id[top[u]], id[u], 1, n));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ret = max(ret, query_max(id[u], id[v], 1, n));
return ret;
}
int query_sum(int u, int v)
{
int ret = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret += query_sum(id[top[u]], id[u], 1, n);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ret += query_sum(id[u], id[v], 1, n);
return ret;
}
// Segment Tree
#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, mid, lson
#define Rson mid + 1, r, rson
int sumv[maxn << 2], maxv[maxn << 2];
inline void pushup(int rt)
{
sumv[rt] = sumv[lson] + sumv[rson];
maxv[rt] = max(maxv[lson], maxv[rson]);
}
void build(int l, int r, int rt = 1)
{
if (l == r)
{
sumv[rt] = maxv[rt] = val[l];
return;
}
int mid = l + r >> 1;
build(Lson), build(Rson);
pushup(rt);
}
void update(int p, int v, int l, int r, int rt = 1)
{
if (l == r)
{
sumv[rt] = maxv[rt] = v;
return;
}
int mid = l + r >> 1;
if (p <= mid)
update(p, v, Lson);
else
update(p, v, Rson);
pushup(rt);
}
int query_max(int L, int R, int l, int r, int rt = 1)
{
if (L <= l && r <= R) return maxv[rt];
int mid = l + r >> 1, ret = -INF;
if (L <= mid) ret = max(ret, query_max(L, R, Lson));
if (mid < R) ret = max(ret, query_max(L, R, Rson));
return ret;
}
int query_sum(int L, int R, int l, int r, int rt = 1)
{
if (L <= l && r <= R) return sumv[rt];
int mid = l + r >> 1, ret = 0;
if (L <= mid) ret += query_sum(L, R, Lson);
if (mid < R) ret += query_sum(L, R, Rson);
return ret;
}
} T;

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
scanf("%d", &n);
T.init(n);
for (int i = 1; i < n; i++)
{
static int u, v;
scanf("%d%d", &u, &v);
T.add_edge(u, v);
}
T.dfs(1, 1, 1);
T.link(1, 1);
T.getval();
T.build(1, n);
int m;
scanf("%d", &m);
while (m--)
{
static char op[10];
static int u, v;
scanf("%s%d%d", op, &u, &v);
if (!strcmp(op, "CHANGE")) T.update(u, v);
if (!strcmp(op, "QMAX")) printf("%d\n", T.query_max(u, v));
if (!strcmp(op, "QSUM")) printf("%d\n", T.query_sum(u, v));
}
return 0;
}
捐助作者
0%