2020牛客NOIP赛前集训营-提高组（第三场）C 牛半仙的妹子Tree

先吐槽一波出题人(

数据强度属实不行，同学写的暴力竟然拿了 $90pts$ 。

读完题发现可以点分树做掉，但是不大会写，所以写了对操作序列分块的做法。

考虑朴素判断某个点是否染色，遍历上次清零操作之后的所有插入操作，如果 $Dis(point_{last}, point_{now}) <= tim_{now} - tim_{last}$ ，那么现在的点可以被染色。

这样考虑对操作序列分块，块大小为 $b$ ，插入操作对某个询问操作的影响分为两种：同在一个块内的和在之前的块里的。

对于这两种插入操作的影响分别计算，对于在同一个块内的就按照上面所说的朴素做法 $O(b)$ 遍历所有在它之前的插入操作；对于块外的插入操作，如果能算出仅有那些操作当前点最早能在什么时间被染色就可以 $O(1)$ 判断。

假设该块之前的都已经算完了，那么现在只需要把当前块的所有操作加入影响中，我们要算出整棵树在所有操作影响下最早被染色，枚举插入操作的时间，把当前块的所有插入操作加入队列，进行 $Bfs$ ，如果插入操作会使某个点最早被染色时间更早就修改，否则不修改，枚举完时间后将队列中剩下的点继续扩展直到遍历整棵树。

这样每次修改的时间是 $O(n)$ 的。

最后考虑块大小，一共有 $m / b$ 个块，每次进行 $O(n)$ 的修改，一共有 $m$ 个询问，每次 $O(b)$ 的遍历所在块，所有有等式：

$\frac{m}{b} \times n = m \times b$

这样计算出块大小是 $\sqrt n$ 的，当然适当调整块大小可能会跑的更块，总时间复杂度 $O(m\sqrt n)$ 。

/*
    _______                       _______                         _______
   / _____ \                     / _____ \                       / _____ \
  / /     \_\  _     __     _   / /      \ \   _     __     _   / /     \_\
 | |          | |   |  |   | | | |        | | | |   |  |   | | | |
 | |          | |   |  |   | | | |     __ | | | |   |  |   | | | |
 | |       __ \  \  |  |  /  / | |     \ \| | \  \  |  |  /  / | |       __
  \ \_____/ /  \  \/ /\ \/  /   \ \_____\  /   \  \/ /\ \/  /   \ \_____/ /
   \_______/    \___/  \___/     \______/\__\   \___/  \___/     \_______/
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

const int N = 200000;
const int INF = 0x7fffffff;

int n, m, len, l[N + 50], r[N + 50], num, ql, tim[N + 50], maxson[N + 50], head[N + 50], dep[N + 50], dfn[N + 50], dfc, st[N + 50][25], lg[N + 50], f[N + 50], cz[N + 50];

struct OP
{
    int op, x;
} op[N + 50];

struct Node
{
    int next, to;
} edge[N * 2 + 50];

void Addedge(int u, int v)
{
    edge[++num] = (Node){head[u], v};
    head[u] = num;
    return;
}

void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? - x : x;
    return;
}

void Dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    f[u] = fa;
    dfn[u] = ++dfc;
    st[dfc][0] = u;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa)
            continue;
        Dfs(v,u);
        st[++dfc][0] = u;
    }
    return;
}

void Calc()
{
    lg[1] = 0;
    for (int i = 2; i <= dfc; i++)
        lg[i] = lg[i / 2] + 1;
    for (int i = 1; (1 << i) <= dfc; i++)
        for (int j = 1; j + (1 << i) - 1 <= dfc; j++)
        {
            int u = st[j][i - 1], v = st[j + (1 << (i - 1))][i - 1];
            if (dep[u] < dep[v])
                st[j][i] = u;
            else
                st[j][i] = v;
        }
    return;
}

int Lca(int x,int y)
{
    int u = dfn[x], v = dfn[y];
    if (u > v)
        swap(u,v);
    int len = lg[v - u + 1];
    int uu = st[u][len],vv = st[v - (1 << len) + 1][len];
    if (dep[uu] < dep[vv])
        return uu;
    else
        return vv;
}

int Dis(int x,int y)
{
    return dep[x] + dep[y] - 2 * dep[Lca(x, y)];
}

queue<int> q;

int main()
{
    Read(n); Read(m);
    for (int i = 1; i <= n; i++) tim[i] = INF;
    for (int i = 1, u, v; i <= n - 1; i++) Read(u), Read(v), Addedge(u, v), Addedge(v, u);
    for (int i = 1; i <= m; i++) Read(op[i].op), Read(op[i].x);
    Dfs(1, 0); Calc(); 
    len = sqrt(n); 
    num = m / len;
    if (num * len < m) num++;
    for (int i = 1; i <= num; i++) l[i] = len * (i - 1) + 1, r[i] = len * i;
    r[num] = m;
    for (int i = 1; i <= num; i++)
    {
    //    cout << l[i] << " " << r[i] << endl;
    //    for (int j = 1; j <= n; j++) printf("%d ", tim[j]); puts("");
        for (int j = l[i]; j <= r[i]; j++)
        {
            if (op[j].op == 1) continue;
            if (op[j].op == 2) ql = j;
            else
            {
        //        cout << j << endl;
                int flag = 0;
                for (int k = max(ql + 1, l[i]); k <= j - 1; k++)
                    if (op[k].op == 1 && j - k >= Dis(op[k].x, op[j].x)) { flag = 1; break; }
            //    cout << flag << endl;
                if (ql < l[i] && tim[op[j].x] <= j) flag = 1;
                puts(flag ? "wrxcsd" : "orzFsYo");                        
            }
        }
        while (!q.empty()) q.pop();
        if (ql >= l[i]) for (int j = 1; j <= n; j++) tim[j] = INF;
        for (int j = max(l[i], ql + 1); j <= r[i]; j++)
        {
            if (op[j].op == 1 && j < tim[op[j].x]) 
            {
                tim[op[j].x] = j;
                q.push(op[j].x);
            }
            while (!q.empty())
            {
                int u = q.front(); if (tim[u] > j) break; q.pop();
                for (int cwq = head[u]; cwq; cwq = edge[cwq].next)
                {
                    int v = edge[cwq].to;
                    if (tim[u] + 1 < tim[v])
                    {
                        tim[v] = tim[u] + 1;
                        q.push(v);
                    }
                }
                 if (tim[u] + 1 < tim[f[u]] && f[u])
                 {
                     tim[f[u]] = tim[u] + 1;
                     q.push(f[u]);
                }
            }
        }    while (!q.empty())
            {
                int u = q.front(); q.pop();
                for (int cwq = head[u]; cwq; cwq = edge[cwq].next)
                {
                    int v = edge[cwq].to;
                    if (tim[u] + 1 < tim[v])
                    {
                        tim[v] = tim[u] + 1;
                        q.push(v);
                    }
                }
                 if (tim[u] + 1 < tim[f[u]] && f[u])
                 {
                     tim[f[u]] = tim[u] + 1;
                     q.push(f[u]);
                }
            }
    }
    return 0;
}