Tree POJ - 3237 边权模板题

题意

三种操作:

  1. 改变某条边的权值
  2. 将a到b点链上的所有边的权值都取反
  3. 查询a到b点链上的所有边的权值最大值

分析

将边权下放到点权,注意查询和修改的时候不能动最后的LCA(因为它的权值是属于它与它父亲的边

轻重链剖分后线段树维护即可。

代码

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
// ybmj
// #include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
int a[maxn];
struct Node {
int Min, Max;
};
struct Edge {
int u, v, w;
};
vector<Edge> edges;
struct HLD {
int n, dfn;
int sz[maxn], top[maxn], son[maxn], dep[maxn], par[maxn], id[maxn],
rk[maxn];
Node seg[maxn << 2];
int lazy[maxn << 2];
vector<int> G[maxn];
void init(int n) {
this->n = n;
clr(son, -1);
dfn = 0;
for (int i = 0; i <= n; i++) G[i].clear();
}
void addedge(int u, int v) {
G[u].pb(v);
G[v].pb(u);
}
void dfs(int u, int fa, int d) {
dep[u] = d;
par[u] = fa;
sz[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa) 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] = ++dfn;
rk[dfn] = u;
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 != par[u]) link(v, v);
}
}
int pushup(int rt) {
seg[rt].Min = min(seg[lson].Min, seg[rson].Min);
seg[rt].Max = max(seg[lson].Max, seg[rson].Max);
}
void build(int l, int r, int rt) {
lazy[rt] = 0;
if (l == r) {
seg[rt].Min = seg[rt].Max = a[l];
return;
}
int m = l + r >> 1;
build(l, m, lson);
build(m + 1, r, rson);
pushup(rt);
}
void pushdown(int rt) {
if (!lazy[rt]) return;
swap(seg[lson].Max, seg[lson].Min);
seg[lson].Max *= -1;
seg[lson].Min *= -1;
swap(seg[rson].Max, seg[rson].Min);
seg[rson].Max *= -1;
seg[rson].Min *= -1;
lazy[lson] ^= 1;
lazy[rson] ^= 1;
lazy[rt] = 0;
}
void update(int l, int r, int L, int R, int rt, int op, int val) {
if (L <= l && R >= r) {
if (!op) {
seg[rt].Max = seg[rt].Min = val;
} else {
swap(seg[rt].Max, seg[rt].Min);
seg[rt].Max *= -1;
seg[rt].Min *= -1;
lazy[rt] ^= 1;
}
return;
}
pushdown(rt);
int m = l + r >> 1;
if (L <= m) update(l, m, L, R, lson, op, val);
if (R > m) update(m + 1, r, L, R, rson, op, val);
pushup(rt);
}
void update_path(int u, int v, int op) {
if (!op) {
update(1, n, id[u], id[u], 1, op, v);
return;
}
if (dep[u] > dep[v]) swap(u, v);

while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, n, id[top[u]], id[u], 1, op, -1);
u = par[top[u]];
}
if(u == v) return;
if (dep[u] > dep[v]) swap(u, v);
update(1, n, id[u] + 1, id[v], 1, op, -1);
}
int query(int l, int r, int L, int R, int rt) {
if (L <= l && R >= r) {
return seg[rt].Max;
}
pushdown(rt);
int m = l + r >> 1;
int ret = NINF;
if (L <= m) ret = max(ret,query(l, m, L, R, lson));
if (R > m) ret = max(ret,query(m + 1, r, L, R, rson));
return ret;
}
int query_path(int u, int v) {
int ret = NINF;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = max(ret, query(1, n, id[top[u]], id[u], 1));
u = par[top[u]];
}
if(u == v) return ret;
if (dep[u] > dep[v]) swap(u, v);
ret = max(ret, query(1, n, id[u] + 1, id[v], 1));
return ret;
}
};
HLD hld;

int main() {
/*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
*/
std::ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int n, u, v, w;
cin >> n;
hld.init(n);
edges.clear();
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
hld.addedge(u, v);
edges.push_back({u, v, w});
}
hld.dfs(1, 1, 1);
hld.link(1, 1);
for (int i = 0; i < edges.size(); i++) {
int &u = edges[i].u;
int &v = edges[i].v;
w = edges[i].w;
if (hld.dep[u] > hld.dep[v]) swap(u, v);
a[hld.id[v]] = w;
}
hld.build(1, n, 1);
string op;
while (cin >> op) {
if (op == "DONE") break;
if (op == "QUERY") {
cin >> u >> v;
cout << hld.query_path(u, v) << endl;
} else if (op == "CHANGE") {
cin >> u >> w;
hld.update_path(edges[u - 1].v, w, 0);
} else {
cin >> u >> v;
hld.update_path(u, v, 1);
}
}
}
}
Thank you for your support!