Chro's Blog


Those things that hurt, instruct.


「HDU 5002」Tree

  1. 1. Problem Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem Description

You are given a tree with N nodes which are numbered by integers 1..N. Each node is associated with an integer as the weight.

Your task is to deal with M operations of 4 types:

  1. Delete an edge (x, y) from the tree, and then add a new edge (a, b). We ensure that it still constitutes a tree after adding the new edge.
  2. Given two nodes a and b in the tree, change the weights of all the nodes on the path connecting node a and b (including node a and b) to a particular value x.
  3. Given two nodes a and b in the tree, increase the weights of all the nodes on the path connecting node a and b (including node a and b) by a particular value d.
  4. Given two nodes a and b in the tree, compute the second largest weight on the path connecting node a and b (including node a and b), and the number of times this weight occurs on the path. Note that here we need the strict second largest weight. For instance, the strict second largest weight of {3, 5, 2, 5, 3} is 3.

Input

The first line contains an integer T (T<=3), which means there are T test cases in the input.

For each test case, the first line contains two integers N and M (N, M<=10^5). The second line contains N integers, and the i-th integer is the weight of the i-th node in the tree (their absolute values are not larger than 10^4).

In next N-1 lines, there are two integers a and b (1<=a, b<=N), which means there exists an edge connecting node a and b.

The next M lines describe the operations you have to deal with. In each line the first integer is c (1<=c<=4), which indicates the type of operation.

  • If c = 1, there are four integers x, y, a, b (1<= x, y, a, b <=N) after c.
  • If c = 2, there are three integers a, b, x (1<= a, b<=N, |x|<=10^4) after c.
  • If c = 3, there are three integers a, b, d (1<= a, b<=N, |d|<=10^4) after c.
  • If c = 4 (it is a query operation), there are two integers a, b (1<= a, b<=N) after c.

All these parameters have the same meaning as described in problem description.

Output

For each test case, first output “Case #x:” (x means case ID) in a separate line.

For each query operation, output two values: the second largest weight and the number of times it occurs. If the weights of nodes on that path are all the same, just output “ALL SAME” (without quotes).

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3 2
1 1 2
1 2
1 3
4 1 2
4 2 3
7 7
5 3 2 1 7 3 6
1 2
1 3
3 4
3 5
4 6
4 7
4 2 6
3 4 5 -1
4 5 7
1 3 4 2 4
4 3 6
2 3 6 5
4 3 6

Sample Output

1
2
3
4
5
6
7
8
Case #1:
ALL SAME
1 2
Case #2:
3 2
1 1
3 2
ALL SAME

Solution

鞍山赛区是什么鬼辣???


「增删边」操作已经告诉我们本题就是 LCT……

而维护次大值的话,只需要同时记录最大值和次大值的信息就行了。这一点跟归并排序有点像 2333

T 了一发发现忘记删文件 IO 了 2333333333333333

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int inf = 2147483647;
struct bst {
bst *par, *ch[2];
int flip, setf, addf, size, val;
int max1, max2, cnt1, cnt2;
void setv(int v) {
setf = val = v;
max1 = v, cnt1 = size;
max2 = -inf, cnt2 = 0;
addf = 0;
}
void addv(int v) {
if (setf > -inf) setv(setf + v);
else {
addf += v, val += v;
if (max1 > -inf) max1 += v;
if (max2 > -inf) max2 += v;
}
}
void reverse() {
flip ^= 1;
swap(ch[0], ch[1]);
}
void maintain();
void pushdown();
void update(int x, int c) {
if (x == -inf) return;
if (x > max1) {
max2 = max1, cnt2 = cnt1;
max1 = x, cnt1 = c;
} else if (x == max1) cnt1 += c;
else if (x > max2) max2 = x, cnt2 = c;
else if (x == max2) cnt2 += c;
}
bool root();
} *null, *id[maxn];
int n, m, a[maxn];
bool bst::root() { return par->ch[0] != this && par->ch[1] != this; }
void bst::maintain() {
size = ch[0]->size + ch[1]->size + 1;
max1 = val, cnt1 = 1, max2 = -inf, cnt2 = 0;
update(ch[0]->max1, ch[0]->cnt1), update(ch[0]->max2, ch[0]->cnt2);
update(ch[1]->max1, ch[1]->cnt1), update(ch[1]->max2, ch[1]->cnt2);
}
void bst::pushdown() {
if (!root()) par->pushdown();
if (flip) {
if (ch[0] != null) ch[0]->reverse();
if (ch[1] != null) ch[1]->reverse();
flip = 0;
}
if (setf > -inf) {
if (ch[0] != null) ch[0]->setv(setf);
if (ch[1] != null) ch[1]->setv(setf);
setf = -inf;
}
if (addf) {
if (ch[0] != null) ch[0]->addv(addf);
if (ch[1] != null) ch[1]->addv(addf);
addf = 0;
}
}
void rotate(bst *o, int d) {
bst *k = o->ch[!d];
o->ch[!d] = k->ch[d];
k->ch[d]->par = o;
k->ch[d] = o;
k->par = o->par;
if (o->par->ch[0] == o) o->par->ch[0] = k;
else if (o->par->ch[1] == o) o->par->ch[1] = k;
o->par = k;
o->maintain();
}
void splay(bst *o) {
o->pushdown();
while (!o->root()) {
bst *y = o->par, *z = y->par;
int d = o == y->ch[0] ? 1 : 0;
if (y == z->ch[!d]) rotate(z, d);
rotate(y, d);
}
o->maintain();
}
void access(bst *o) {
bst *tmp = null;
while (o != null) {
splay(o);
o->ch[1] = tmp;
o->maintain();
tmp = o;
o = o->par;
}
}
void evert(bst *o) {
access(o);
splay(o);
o->reverse();
}
void link(bst *x, bst *y) {
evert(y);
y->par = x;
}
void cut(bst *x, bst *y) {
evert(x);
access(y);
splay(y);
y->ch[0] = x->par = null;
y->maintain();
}
bst *split(bst *x, bst *y) {
evert(x);
access(y);
splay(y);
return y;
}
void path_add(bst *x, bst *y, int v) { split(x, y)->addv(v); }
void path_set(bst *x, bst *y, int v) { split(x, y)->setv(v); }
int read() {
int ret = 0, flag = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
for (; isdigit(ch); ch = getchar()) (ret *= 10) += ch - '0';
return ret * flag;
}
void init() {
null = new bst;
null->par = null->ch[0] = null->ch[1] = null;
null->flip = null->addf = 0;
null->setf = null->max1 = null->max2 = null->val = -inf;
null->cnt1 = null->cnt2 = null->size = 0;
}
void reset() {
for (int i = 1; i <= n; ++i) {
if (!id[i]) id[i] = new bst;
id[i]->par = id[i]->ch[0] = id[i]->ch[1] = null;
id[i]->flip = id[i]->addf = 0;
id[i]->setf = -inf;
id[i]->val = a[i];
id[i]->max1 = a[i], id[i]->cnt1 = id[i]->size = 1;
id[i]->max2 = -inf, id[i]->cnt2 = 0;
}
}
int main() {
init();
for (int T = read(), kase = 1; kase <= T; ++kase) {
printf("Case #%d:\n", kase);
n = read(), m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
reset();
for (int i = 1; i < n; ++i) link(id[read()], id[read()]);
for (++m; --m; ) {
int c = read(), a = read(), b = read();
if (c == 1) cut(id[a], id[b]), link(id[read()], id[read()]);
else if (c == 2) path_set(id[a], id[b], read());
else if (c == 3) path_add(id[a], id[b], read());
else {
bst *ans = split(id[a], id[b]);
printf(ans->max2 == -inf ? "ALL SAME\n" : "%d %d\n", ans->max2, ans->cnt2);
}
}
}
return 0;
}
最近的文章

「BZOJ 1367」「Baltic2004」sequence

Description Input Output一个整数R Sample Input12345678794820141518 Sample Output113 HINT所求的Z序列为6,7,8,13,14,15,18. R=13 Solution2005 年国家集训队论文题。 首先将所有元素减去其…

BZOJ, 可合并堆 继续阅读
更早的文章

「BZOJ 4006」「LNOI/JLOI2015」通道连接

题目描述小铭铭最近进入了某情报部门,该部门正在被如何建立安全的通道连接困扰。 该部门有 n 个情报站,用 1 到 n 的整数编号。给出 m 对情报站 ui, vi 和费用 wi,表示情报站 ui 和 vi 之间可以花费 wi 单位资源建立通道。 如果一个情报站经过若干个建立好的通道可以到达另外一个情…

BZOJ, 斯坦纳树, 状压 DP 继续阅读