http://codeforces.com/contest/343

前三题水题。

D题
利用一个重要性质即可秒:若一颗子树的某个节点为空,那么其父节点也为空。
首先dfs一下弄出时间戳,然后用一个set维护空节点。
2号操作直接把节点v插到set中。
1号操作先看看以当前节点的父亲为根的子树是否含有空节点,有则把父亲插入到set中。
3号操作,看当前节点及后代中有没有空节点即可。

代码:

/* 1496 ms, 43200 KB */
#include <bits/stdc++.h>
using namespace std;
const int mx = 5e5 + 5;

vector<int> g[mx];
set<int> Empty;
int L[mx], R[mx], fa[mx];
int timer, to;

void dfs(int v, int p = -1)
{
    L[v] = ++timer;
    for (int i = 0; i < g[v].size(); ++i)
        if ((to = g[v][i]) != p)
            fa[to] = v, dfs(to, v);
    R[v] = timer;
    if (R[v] - L[v] == 1) Empty.insert(L[v]); // 叶节点
}

bool empty(int v)
{
    set<int>::iterator it = Empty.lower_bound(L[v]);
    return it != Empty.end() && *it <= R[v];
}

int main()
{
    int n, q, a, b, op, v;
    scanf("%d", &n);
    while (--n)
    {
        scanf("%d%d", &a, &b);
        g[a].push_back(b), g[b].push_back(a);
    }
    dfs(1);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d", &op, &v);
        if (op == 1)
        {
            if (fa[v] && empty(fa[v])) Empty.insert(L[fa[v]]); // 下面有空节点,说明父亲也是空节点
            Empty.erase(Empty.lower_bound(L[v]), Empty.upper_bound(R[v])); // 灌水,即清空空节点
        }
        else if (op == 2) Empty.insert(L[v]); // v及其父亲为空,利用时间戳的性质,我们只需要记录v节点为空即可
        else puts(empty(v) ? "0" : "1");
    }
    return 0;
}

Comments

comments powered by Disqus