【題目敘述】https://codeforces.com/contest/343/problem/D
【解題想法】線段樹(Segment Tree) + 樹壓平
- vector<int> g[maxn]：存圖
- p[x]：節點 x 的parent
- in[x], out[x]：樹壓平後，節點 x 與其子樹在樹上的進出序位。
- water[maxn<<2]：線段樹上各區間的值(有水 or 沒有水)
- lazy[maxn<<2]：lazy tag，標註有水尚未往下流。
- 函式 dfs( )：樹上的DFS，找出「前序序位」。【參考】
- 函式 pull( )：左右兒子都有水，自己才有水（Line-28）。
- 函式 fill( )：加水，水該往下流，但只先加上lazy tag（Line-32/33）。
- 函式 empty( )：放水（Line-48）。若牽涉到左右兒子，記得先push( )處理lazy tag，免得殘留的過去的加水紀錄影響結果。
- 【關鍵】 Line-92：加水之前，如果發現其子樹是空的且有父節點，要先把父節點的水倒空，再加水。
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 500005;
int n, in[maxn], out[maxn], p[maxn], idx, water[maxn<<2], lazy[maxn<<2], q, c, v;
vector <int> g[maxn];
void dfs(int now, int pre){
in[now] = ++idx;
for (auto nxt:g[now]){
if (nxt == pre) continue;
p[nxt] = now; //parent
dfs(nxt, now);
}
out[now] = idx;
}
void push(int x){
if (lazy[x]){
lazy[x<<1] = 1;
lazy[x<<1|1] = 1;
water[x<<1] = 1;
water[x<<1|1] = 1;
lazy[x] = 0;
}
}
void pull(int x){
water[x] = water[x<<1] & water[x<<1|1];
}
void fill(int x, int l, int r, int ql, int qr){
if (ql <= l && r <= qr){
water[x] = 1;
lazy[x] = 1;
return;
}
push(x);
int mid = (l+r) >> 1;
if (ql <= mid){
fill(x<<1, l, mid, ql, qr);
}
if (mid < qr){
fill(x<<1|1, mid+1, r, ql, qr);
}
pull(x);
}
void empty(int x, int l,int r, int pos){
if (l == r){
water[x] = 0;
return;
}
push(x);
int mid = (l+r) >> 1;
if (pos <= mid){
empty(x<<1, l, mid, pos);
}else{
empty(x<<1|1, mid+1, r, pos);
}
pull(x);
}
int query(int x, int l, int r, int ql, int qr){
if (ql <= l && r <= qr){
return water[x];
}
push(x);
int mid = (l + r) >> 1;
int ret = 1;
push(x);
if (ql <= mid){
ret = ret & query(x<<1, l, mid, ql, qr);
}
if (qr > mid){
ret = ret & query(x<<1|1, mid+1, r, ql, qr);
}
return ret;
}
int main() {
cin >> n;
int a, b;
for (int i = 1; i < n; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
p[1] = 0;
dfs(1, 0);
cin >> q;
while (q--){
cin >> c >> v;
if (c == 1) {
if (!query(1, 1, n, in[v], out[v]) && p[v]){
empty(1, 1, n, in[p[v]]);
}
fill(1, 1, n, in[v], out[v]);
}
else if (c == 2){
empty(1, 1, n, in[v]);
}
else cout << query(1, 1, n, in[v], out[v]) << '\n';
}
}