目录

  1. 引言
  2. BZOJ 3319: 黑白树
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 3319: 黑白树 题解

BZOJ 3319: 黑白树

  • Time Limit: 10 Sec

  • Memory Limit: 512 MB

Description

给定一棵树,边的颜色为黑或白,初始时全部为白色。维护两个操作:

1.查询u到根路径上的第一条黑色边的标号。
2.将u到v 路径上的所有边的颜色设为黑色。

Notice:这棵树的根节点为1

Input

第一行两个数n,m分别表示点数和操作数。
接下来n-? 1行,每行2个数u,v.表示一条u到v的边。
接下来m行,每行为以下格式:

1 v 表示第一个操作

2 v u 表示第二种操作

Output

对于每个询问,输出相应答案。如果不存在,输出0。

Sample Input

5 4

1 2

1 3

2 4

2 5

1 2

2 2 3

1 3

1 4

Sample Output

0

2

1

HINT

对于 100% 的数据:n,m<=10^6

题目分析

显然是一道ZZ的树链剖分题……但是我TM居然WA了好几次,我们只需要记录一下每个点的父亲边编号,然后每次染黑的时候除了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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#define maxn 2000005
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define erep(i, x) for (register int i = h[x]; i; i = e[i].next)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') ch = gc(), f = 0;
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
struct edge{
int next, to;
edge(int next, int to) : next(next), to(to){}
edge(){}
}e[maxn];
int cnt = 1, h[maxn];
void Add_Edge(int x, int y){
e[++cnt] = edge(h[x], y);
h[x] = cnt;
e[++cnt] = edge(h[y], x);
h[y] = cnt;
}
int fa[maxn];
int son[maxn];
int siz[maxn];
int top[maxn];
int dfs[maxn];
int idfs[maxn];
int d[maxn];
int num[maxn];
int t = 0;
void DFS(int x){
siz[x] = 1;
erep(i, x){
int op = e[i].to;
if (op == fa[x]) {num[x] = i >> 1; continue;}
fa[op] = x;
d[op] = d[x] + 1;
DFS(op);
siz[x] += siz[op];
if (siz[op] > siz[son[x]]) son[x] = op;
}
}
void DFS(int x, int tp){
top[x] = tp;
dfs[x] = ++t;
idfs[t] = x;
if (son[x]) DFS(son[x], tp);
erep(i, x){
int op = e[i].to;
if (op == fa[x] || op == son[x]) continue;
DFS(op, op);
}
}
void init(){
DFS(1);
DFS(1, 1);
}
int sum[maxn << 1];
int qx, qy, qd;
void set(int l, int r, int o){
if (sum[o] == r - l + 1) return;
if (l == r) {sum[o] = 1; return;}
int mid = ((r - l) >> 1) + l;
if (qx <= mid) set(l, mid, o << 1);
if (qy > mid) set(mid + 1, r, o << 1 | 1);
sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
int find(int l, int r, int o){
if (l == r) return (sum[o]) ? num[idfs[l]] : 0;
if (qx <= l && r <= qy){
int mid = ((r - l) >> 1) + l;
if (sum[o << 1 | 1]) return find(mid + 1, r, o << 1 | 1);
return find(l, mid, o << 1);
}
int mid = ((r - l) >> 1) + l;
int d = 0;
if (qy > mid) d = find(mid + 1, r, o << 1 | 1);
if (d) return d;
return (qx <= mid) ? find(l, mid, o << 1) : 0;
}
void set(int x, int y){
int a = top[x], b = top[y];
while (a != b){
if (d[a] < d[b]) swap(x, y), swap(a, b);
qx = dfs[a], qy = dfs[x];
set(1, n, 1);
x = fa[a], a = top[x];
}
if (d[x] < d[y]) swap(x, y);
qx = dfs[y] + 1, qy = dfs[x];
if (qx <= qy) set(1, n, 1);
}
int get(int x){
int a = top[x];
while (x){
qx = dfs[a], qy = dfs[x];
int d = find(1, n, 1);
if (d) return d;
else x = fa[a], a = top[x];
}
return 0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("bw.in", "r", stdin);
#endif
int x, y, op;
read(n), read(m);
rep(i, 1, n - 1) read(x), read(y), Add_Edge(x, y);
init();
rep(i, 1, m){
read(op);
if (op == 1) read(x), printf("%d\n", get(x));
else if (op == 2) read(x), read(y), set(x, y);
else assert(false);
}
return 0;
}