「Query on a tree」

题目名称 概述
Query on a tree I 维护一棵树,支持修改边权和路径最大值查询
Query on a tree II 维护一棵树,支持链上求和,链上第 K 个位置查询
Query on a tree III 维护一棵树,支持查询子树中的第 K 小节点
Query on a tree again 维护一棵树,支持查询链上深度最小有效节点
Query on a tree IV 维护一棵树,支持查询树上有效点对间的最大距离

Query on a tree I

Query on a tree II

Query on a tree III

Query on a tree again!

Query on a tree IV

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.

We will ask you to perfrom some instructions of the following form:

  • C a : change the color of node a.(from black to white or from white to black)
  • A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

题意

维护一个边带权,点带色的树,支持修改点的颜色以及查询树上最长距离

题解

代码1

  • 自己打的垃圾点分治,被卡 $TLE$,暂时无法 $AC$
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
202
#pragma GCC optmize ("O2")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef __gnu_pbds::priority_queue<int> pqi;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
namespace Solve {
vector<pii>G[maxn];
void add(int x, int y, int z) {
G[x].push_back(make_pair(y, z));
G[y].push_back(make_pair(x, z));
}
vector<pqi>null(maxn * 60); int coc = 2;
vector<int>q1[maxn], q2[maxn];
int ans = 0, del = 1;
int top[maxn][20], who[maxn][20], size[maxn], maxs[maxn], root, all, cnt;
ll dis[maxn][20];
bool vis[maxn], color[maxn];
void getroot(int u, int f) {
size[u] = 1; maxs[u] = 0;
for (int i = G[u].size() - 1; ~i; i--) {
int v = G[u][i].first;
if (v == f || vis[v]) continue;
getroot(v, u); size[u] += size[v];
maxs[u] = std::max(maxs[u], size[v]);
}
maxs[u] = std::max(maxs[u], all - size[u]);
if (maxs[root] > maxs[u]) root = u;
}
void Push(int id, int v) {
null[id].push(v);
}
ll Top(int id) {
return null[id].size() ? null[id].top() : 0;
}
void Pop(int id) {
if (null[id].size()) null[id].pop();
}
int Size(int id) {
return null[id].size();
}
void link(int u, int f, int h, ll d, int p) {
top[u][++top[u][0]] = h;
who[u][++who[u][0]] = p;
dis[u][++dis[u][0]] = d;
Push(q1[h][p], d);
for (int i = G[u].size() - 1; ~i; i--) {
int v = G[u][i].first;
if (v == f || vis[v]) continue;
link(v, u, h, d + G[u][i].second, p);
}
}
int gettop(int xx, int yy) {
pqi &x = null[xx], &y = null[yy];
while (x.size() && y.size() &&
x.top() == y.top()) x.pop(), y.pop();
if (!x.size()) return 0; return x.top();
}
void dfs(int u) {
vis[u] = true;
q1[u].push_back(coc++);
q2[u].push_back(coc++);
Push(q1[u][0], 0);
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first;
q1[u].push_back(coc++);
q2[u].push_back(coc++);
if (vis[v]) continue;
link(v, u, u, G[u][i].second, i + 1);
Push(q1[u][0], Top(q1[u][i + 1]));
}
ll val1 = gettop(q1[u][0], q2[u][0]);
Pop(q1[u][0]);
ll val2 = gettop(q1[u][0], q2[u][0]);
Push(q1[u][0], val1);
Push(ans, val1 + val2);
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first;
if (vis[v]) continue;
all = size[v]; root = 0;
getroot(v, u);
int p = root; dfs(p);
}
}
void build(int n) {
cnt = all = n; maxs[root = 0] = n;
getroot(1, 0); int p = root; dfs(p);
}
int query() {
if (!cnt) return -1;
return gettop(ans, del);
}
void change(int u) {
if (color[u]) {
cnt++;
Push(q1[u][0], 0);
for (int i = 1; i <= top[u][0]; i++) {
int v = top[u][i], w = who[u][i];
if (Size(q1[v][0]) - Size(q2[v][0]) >= 2) {
int val1 = gettop(q1[v][0], q2[v][0]);
Pop(q1[v][0]);
int val2 = gettop(q1[v][0], q2[v][0]);
Push(del, val1 + val2); Push(q1[v][0], val1);
}
if (Size(q1[v][w]) - Size(q2[v][w]) == 0)
Push(q1[v][0], dis[u][i]), Push(q1[v][w], dis[u][i]);
else {
Push(q2[v][0], gettop(q1[v][w], q2[v][w]));
Push(q1[v][w], dis[u][i]);
Push(q1[v][0], gettop(q1[v][w], q2[v][w]));
}
if (Size(q1[v][0]) - Size(q2[v][0]) >= 2) {
int val1 = gettop(q1[v][0], q2[v][0]);
Pop(q1[v][0]);
int val2 = gettop(q1[v][0], q2[v][0]);
Push(ans, val1 + val2); Push(q1[v][0], val1);
}
}
}
else {
cnt--;
Push(q2[u][0], 0);
for (int i = 1; i <= top[u][0]; i++) {
int v = top[u][i], w = who[u][i];
if (Size(q1[v][0]) - Size(q2[v][0]) >= 2) {
int val1 = gettop(q1[v][0], q2[v][0]);
Pop(q1[v][0]);
int val2 = gettop(q1[v][0], q2[v][0]);
Push(del, val1 + val2); Push(q1[v][0], val1);
}
if (Size(q1[v][w]) - Size(q2[v][w]) == 1)
Push(q2[v][0], dis[u][i]), Push(q2[v][w], dis[u][i]);
else {
Push(q2[v][0], gettop(q1[v][w], q2[v][w]));
Push(q2[v][w], dis[u][i]);
Push(q1[v][0], gettop(q1[v][w], q2[v][w]));
}
if (Size(q1[v][0]) - Size(q2[v][0]) >= 2) {
ll val1 = gettop(q1[v][0], q2[v][0]);
Pop(q1[v][0]);
ll val2 = gettop(q1[v][0], q2[v][0]);
Push(ans, val1 + val2); Push(q1[v][0], val1);
}
}
}
color[u] = !color[u];
}
}
int main() {
int n; scanf("%d", &n);
for (int i = 2; i <= n; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
Solve::add(x, y, z);
}
Solve::build(n);
int m; scanf("%d", &m);
while (m--) {
char op[3]; int x;
scanf("%s", op);
if (op[0] == 'A') {
if (!Solve::cnt) printf("They have disappeared.\n");
else printf("%lld\n", Solve::query());
}
if (op[0] == 'C') {scanf("%d", &x); Solve::change(x);}
}
return 0;
}
/*
10
2 1 1
3 2 1
4 2 1
5 1 1
6 2 1
7 5 1
8 1 1
9 3 1
10 7 1
10
A
A
C 6
A
A
C 8
C 8
C 2
A
C 1
*/

代码2

  • $Sengxian$大佬的链分治,详情见 $qzc$ 论文
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
#include <iostream>
#include <queue>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#define nl NULL
#define LL long long
using namespace std;
typedef long long ll;
inline int read() {
int u = 0, f = 1; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) u = u * 10 + c - '0';
return u * f;
}
const int maxn = 1e5 + 10, inf = 0x3f3f3f3f;
struct edge {
int to, cost;
edge(int to, int cost):
to(to), cost(cost) {}
};
vector<edge> G[maxn];
int n, blackCnt;
bool color[maxn];
int fa[maxn], fv[maxn], s[maxn], id[maxn], idR[maxn], bel[maxn], timestamp, sz[maxn];
int sum[maxn], root[maxn];
static const int maxNode = (1 << 17) * 2 + 10;
struct Node {
int maxL, maxR, opt;
Node(int maxL = -inf, int maxR = -inf, int opt = -inf):
maxL(maxL), maxR(maxR), opt(opt) {}
}segs[maxNode];
int ls[maxNode], rs[maxNode], segCnt;
template <typename T>
struct Rint {
bool operator () (const T &l, const T &r) {return l > r;}
};
multiset<int, Rint<int> >ch[maxn], ans;
int dfs1(int u, int f) {
fa[u] = f; s[u] = 1;
for (int i = 0; i < (int)G[u].size(); ++i) {
edge &e = G[u][i];
if (e.to != f) {
fv[e.to] = e.cost;
s[u] += dfs1(e.to, u);
}
}
return s[u];
}
void dfs2(int u, int num) {
idR[timestamp] = u;
id[u] = timestamp++;
bel[u] = num;
sz[num]++;
int Max = 0, idx = -1;
for (int i = 0; i < (int)G[u].size(); ++i) {
edge &e = G[u][i];
if (e.to != fa[u] && s[e.to] > Max)
Max = s[e.to], idx = e.to;
}
if (Max == 0) return;
dfs2(idx, num);
for (int i = 0; i < (int)G[u].size(); ++i) {
edge &e = G[u][i];
if (e.to != fa[u] && e.to != idx)
dfs2(e.to, e.to);
}
}
Node merge(const Node &ln, const Node &rn, int dL, int dMid, int dR) {
Node newNode;
newNode.maxL = max(ln.maxL, dL + rn.maxL);
newNode.maxR = max(rn.maxR, dR + ln.maxR);
newNode.opt = max(max(ln.opt, rn.opt), dMid + ln.maxR + rn.maxL);
return newNode;
}
void maintain(int p, int u) {
int d1 = -inf, d2 = -inf;
if (color[u] == 0) d1 = d2 = 0;
if (ch[u].size()) d1 = max(d1, *(ch[u].begin()));
if (ch[u].size() > 1) d2 = max(d2, *(++ch[u].begin()));
segs[p].maxL = segs[p].maxR = d1;
segs[p].opt = d1 + d2;
if (color[u] == 0) segs[p].opt = max(segs[p].opt, 0);
}
void buildTree(int p, int l, int r) {
if (r - l == 1) {
int u = idR[l];
for (int i = 0; i < (int)G[u].size(); ++i) {
edge &e = G[u][i];
if (e.to != fa[u] && bel[e.to] != bel[u]) {
buildTree(root[e.to] = segCnt++, id[e.to], id[e.to] + sz[e.to]);
ch[u].insert(segs[root[e.to]].maxL + e.cost);
ans.insert(segs[root[e.to]].opt);
}
}
maintain(p, u);
}
else {
int mid = l + r >> 1;
buildTree(ls[p] = segCnt++, l, mid);
buildTree(rs[p] = segCnt++, mid, r);
segs[p] = merge(segs[ls[p]], segs[rs[p]], sum[mid] - sum[l], sum[mid] - sum[mid - 1], sum[r - 1] - sum[mid - 1]);
}
}
vector<int> path;
void findPath(int u) {
while (u != -1) {
path.push_back(u);
u = fa[bel[u]];
}
}
void modify(int p, int l, int r, int idx) {
if (r - l == 1) {
if (idx + 1 != path.size()) {
int nexT = bel[path[idx + 1]], u = idR[l];
ans.erase(ans.find(segs[root[nexT]].opt));
ch[u].erase(ch[u].find(segs[root[nexT]].maxL + fv[nexT]));
modify(root[nexT], id[nexT], id[nexT] + sz[nexT], idx + 1);
ch[u].insert(segs[root[nexT]].maxL + fv[nexT]);
ans.insert(segs[root[nexT]].opt);
}
maintain(p, idR[l]);
}else {
int u = path[idx], mid = l + r >> 1;
if (id[u] < mid) modify(ls[p], l, mid, idx);
else modify(rs[p], mid, r, idx);
segs[p] = merge(segs[ls[p]], segs[rs[p]], sum[mid] - sum[l], sum[mid] - sum[mid - 1], sum[r - 1] - sum[mid - 1]);
}
}
void process() {
dfs1(0, -1); dfs2(0, 0);
for (int i = 0; i < n; ++i)
sum[id[i]] = fv[i];
for (int i = 1; i < n; ++i)
sum[i] += sum[i - 1];
buildTree(root[0] = segCnt++, id[0], id[0] + sz[0]);
}
char op[2];
int main() {
n = read();
memset(color, 0, sizeof(bool) * n);
blackCnt = n;
for (int i = 0; i < n - 1; ++i) {
int f = read() - 1, t = read() - 1, c = read();
G[f].push_back(edge(t, c));
G[t].push_back(edge(f, c));
}
process();
int q = read();
while (q--) {
scanf("%s", op);
if (op[0] == 'C') {
int u = read() - 1;
if (color[u]) blackCnt++;
else blackCnt--;
color[u] = !color[u];
path.clear();
findPath(u);
reverse(path.begin(), path.end());
modify(root[0], id[0], id[0] + sz[0], 0);
}
else {
if (blackCnt == 0) puts("They have disappeared.");
else printf("%d\n", max(*ans.begin(), segs[0].opt));
}
}
return 0;
}

代码3

  • 不知名的神奇代码,速度 $Vjudge~Rank~1$
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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<climits>
#include<iostream>
#define max(a, b) ({int _ = (a), __ = (b); _ > __ ? _ : __;})
#define swap(___, a, b) ({___ _ = (a); (a) = (b); (b) = _;})
#define maxn 204800
#define fort(_, __, ___) for (int _ = (__); _ <= (___); ++_)
#define fot(_, __, ___) for (int _ = (__); _ < (___); ++_)
#define ms(a, b) memset(a, b, sizeof a)
#define openfile() freopen("data.in","r",stdin); freopen("TLE.out","w",stdout);
#define adde(a, b, c) \
({*(++eptr) = (edge){b, c, h[a]}, h[a] = eptr; \
*(++eptr) = (edge){a, c, h[b]}, h[b] = eptr;})
#define abs(_) ({int __ = _; __ < 0 ? -__ : __;})
#define upit(_, __) if (_ -> ans < __ -> ans) _ -> ans = __ -> ans;
struct node {int val, pos; node *f, *c[2];}
heap[maxn << 1], *nptr, *to_heap[maxn], *to_ah[maxn], *null, *hth[maxn], *ansh[maxn];
struct edge {int t, v; edge *nt;}
eg[maxn << 1], *eptr, *h[maxn];
struct tree {int x, y, ans, from; tree *l, *r, *f;}
seg[maxn << 1], *seg_rot[maxn], *to_seg[maxn], *sptr;
const int inf = 100000000; char rd, order; int fu;
inline void read(int &a)
{
a = 0; rd = getchar(); while (('0' > rd || rd > '9') && rd != '-') rd = getchar();
rd == '-' ? fu = -1, rd = getchar() : fu = 1;
while ('0' <= rd && rd <= '9') a *= 10, a += rd - '0', rd = getchar();
a *= fu;
}
typedef int arr[maxn];
arr s, q, ef, aux, l, r, x, y, f, mid, pos, length, weight;
int n, ques, a, u, v, white_num, ans;
bool color[maxn];
inline node *merge(node *a, node *b)
{
if (a == null) return b;
if (b == null) return a;
if (a -> val < b -> val) swap(node *, a, b); a -> f = null;
return b = merge(a -> c[1], b), a -> c[1] = a -> c[0], (a -> c[1] = b) -> f = a;
}
inline node *build_h(int k, node **tt)
{
node *root = null;
for(edge *e = h[k]; e; e = e -> nt)
if (e -> t != aux[k])
root = merge(root, tt[e -> t]);
return root;
}
inline tree *build(int s, int t)
{
if (s == t)
{
tree *p = ++sptr; node *th = to_heap[u] = build_h(u, hth);
int tmp = max(0, th -> val), tmp2 = max(0, max(th -> c[0] -> val, th -> c[1] -> val));
*p = (tree){-pos[u] + tmp, pos[u] + tmp, tmp + tmp2, u, 0, 0, 0};
if (p -> ans < (to_ah[u] = build_h(u, ansh)) -> val) p -> ans = to_ah[u] -> val;
to_seg[u] = p; u = aux[u]; return p;
}
int md = (s + t) >> 1; tree *l = build(s, md), *p = ++sptr, *r = build(md + 1, t);
*p = (tree){max(l -> x, r -> x), max(l -> y, r -> y), l -> x + r -> y, 0, l, r, 0};
if (l -> y > r -> y) p -> from = l -> from; else p -> from = r -> from;
p -> ans = max(max(l -> ans, r -> ans), p -> ans);
l -> f = r -> f = p; upit(p, l); upit(p, r);
// X : -sum[x] + maxlen[x]; Y : sum[y] + maxlen[y];
return p;
}
inline void prepare()
{
read(n); eptr = eg; int a, b, c; tree *tr;
fot(i, 1, n) read(a), read(b), read(c), adde(a, b, c);
int head = 0, tail = 1, maxsize; q[1] = 1;
white_num = n; nptr = heap; sptr = seg; read(ques);
null = heap; *null = (node){-inf, 0, null, {null, null}};
while (head != tail)
{
u = q[++head];
if (h[u] -> t == ef[u]) h[u] = h[u] -> nt;
for(edge *e = h[u]; e; e = e -> nt)
{
ef[q[++tail] = e -> t] = u;
if (e -> nt) if (e -> nt -> t == ef[u]) e -> nt = e -> nt -> nt;
}
}
for(int i = n; i; --i)
{
s[u = q[i]] = 1; maxsize = 0;
for(edge *e = h[u]; e; e = e -> nt)
{
s[u] += s[v = e -> t];
if (s[v] > maxsize) aux[u] = v, maxsize = s[v];
weight[v] = pos[v] = e -> v;
}
}
fort(i, 1, n)
if (!f[u = q[i]])
{
length[u] = 1; pos[u] = 0; f[u] = u;
for(int j = aux[u]; j; j = aux[j])
f[j] = u, ++length[u], pos[aux[j]] += pos[j];
}
for(int i = n; i; --i)
if (f[u = q[i]] == q[i])
{
tr = seg_rot[q[i]] = build(1, length[u]); u = q[i];
*(hth[u] = ++nptr) = (node){tr -> y + weight[u], tr -> from, null, {null, null}};
*(ansh[u] = ++nptr) = (node){tr -> ans, u, null, {null, null}};
}
ans = seg_rot[1] -> ans;
}
inline void up_seg(int u)
{
tree *p = to_seg[u];node *th = to_heap[u];
int tmp = th -> val, tmp2 = max(th -> c[0] -> val, th -> c[1] -> val);
if (!color[u]) {if (tmp < 0) tmp = tmp2 = 0; else if (tmp2 < 0) tmp2 = 0;}
*p = (tree){-pos[u] + tmp, pos[u] + tmp, tmp + tmp2, u, p -> l, p -> r, p -> f};
if (p -> ans < to_ah[u] -> val) p -> ans = to_ah[u] -> val; p = p -> f;
while (p)
{
p -> x = max(p -> l -> x, p -> r -> x);
p -> y = max(p -> l -> y, p -> r -> y);
p -> ans = p -> l -> x + p -> r -> y;
upit(p, p -> l); upit(p, p -> r);
if (p -> y == p -> l -> y) p -> from = p -> l -> from;
else p -> from = p -> r -> from;
p = p -> f;
}
}
inline void getit(int k, node **t, node **t2, int ct, node *&a)
{
node *d, *h, *q;
d = t[k]; h = merge(d -> c[0], d -> c[1]);
d -> c[0] = d -> c[1] = null; d -> val = ct;
if (d -> f == null) h = merge(d, h);
else
{
q = d -> f; q -> c[q -> c[1] == d] = null;
d -> f = null; h = merge(d, merge(t2[ef[k]], h));
}
a = h;
}
inline void fresh(int k)
{
for(;;)
{
up_seg(k); k = f[k]; if (k == 1) break;
getit(k, hth, to_heap, seg_rot[k] -> y + weight[k], to_heap[ef[k]]);
getit(k, ansh, to_ah, seg_rot[k] -> ans, to_ah[ef[k]]); k = ef[k];
}
}
inline void update(int k)
{
if (color[k])
++white_num, color[k] = 0;
else
--white_num, color[k] = 1;
fresh(k); ans = seg_rot[1] -> ans;
}
int main()
{
//int a = GetTickCount();
prepare();
while(ques--)
{
order = getchar(); while (order > 'C' || order < 'A') order = getchar();
if (order == 'A')
if (!white_num)
puts("They have disappeared.");
else
if (white_num == 1)
puts("0");
else
printf("%d\n", ans > 0 ? ans : 0);
else
read(a), update(a);
}
//int b = GetTickCount();
//std::cerr << (b - a) << "ms" << std::endl;
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :