原博客食用效果更佳

一.题目

题目描述
牛半仙的妹子的座位呈一个树状结构，由个点和条边组成，号结点为根。
当牛半仙的一个妹子无视 牛半仙后，一个单位时间后周围的妹子也会无视牛半仙。
有些时候牛半仙为了吸引妹子们的注意，会开启鬼畜模式，这时所有妹子无视牛半仙的状态都会消失，恢复正常，并且这之后的状态不会被之前影响。
牛半仙想知道某个妹子是否无视了他，于是他找到了你，请你帮帮他。
数据范围
传送门

二.Solution

这道题目听说有人在考试的时候一个树剖直接骗90分，这数据。。。好吧。
我也是考试之后才知道要分块的（太弱了），我们直接将分块，分成块，其实怎么分都可以，只要是根号级别的复杂度就行了。然后分类讨论：
先处理出最近的的操作的时间，对于一个的询问，

• ①对于在这个询问之前且在之前且在同一个块内的的询问，求出这个询问的点到当前点的距离，如果这个距离小于等于这两个询问之间相隔的时间，就说明无视会扩展到这个点；
• ②对于在块外的点，如果在当前的块内就说明刷新了的，不用管，否则就判断当前点被无视的时间是否大于当前时间就行了。
  理解一下：

  for (int i = 1; i <= num; i ++){//num代表块数
        for (int j = l[i]; j <= r[i]; j ++){//当前块的范围
            if (q[j].opt == 1)
                continue;
            if (q[j].opt == 2)//找最近哪一次被刷新
                ql = j;
            else{
                bool flag = 0;
                for (int k = max (l[i], ql + 1); k <= j - 1; k ++){
                    if (q[k].opt == 1 && get_dis(q[k].x, q[j].x) <= j - k){//get_dis要用到lca求距离，打个树剖或者Tarjan就行
                        flag = 1;
                        break;
                    }
                }
                if (ql < l[i] && tim[q[j].x] <= j)
                    flag = 1;
                if (flag)
                    printf ("wrxcsd\n");
                else
                    printf ("orzFsYo\n");
            }
        }
    }

  然后问题就来到如何求块外的点感染到其他点的时间。对于每块我们用bfs更新这个块内新的无视的点扩散的情况，这里是的时间复杂度。因为就相当于遍历一遍图，遍历过的点肯定是不会再走的。
  Perfect！

  三.Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

#define M 100005
#define INF 0x3f3f3f3f

struct question{
    int opt, x;
}q[M];
int n, m, dfn[M], cnt, dep[M], fa[M], son[M], siz[M], top[M], l[M], r[M], len, num, ql, tim[M];
vector <int> G[M];
queue <int> Q;

void dfs1 (int x, int fath){
    dep[x] = dep[fath] + 1;
    siz[x] = 1;
    fa[x] = fath;
    int maxn = -1;
    for (int i = 0; i < G[x].size(); i ++){
        int tmp = G[x][i];
        if (tmp != fath){
            dfs1 (tmp, x);
            if (siz[tmp] > maxn)
                maxn = siz[tmp], son[x] = tmp;
            siz[x] += siz[tmp];
        }
    }
}
void dfs2 (int x, int fath){
    top[x] = fath;
    dfn[x] = ++ cnt;
    if (! son[x])
        return ;
    dfs2 (son[x], fath);
    for (int i = 0; i < G[x].size(); i ++){
        int tmp = G[x][i];
        if (tmp != fa[x] && tmp != son[x])
            dfs2 (tmp, tmp);
    }
}
int get_lca (int x, int y){
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]])
            swap (x, y);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        return y;
    return x;
}
int get_dis (int x, int y){
    return dep[x] + dep[y] - 2 * dep[get_lca (x, y)];
}
int main (){
    scanf ("%d %d", &n, &m);
    for (int i = 1; i < n; i ++){
        int u, v;
        scanf ("%d %d", &u, &v);
        G[u].push_back (v);
        G[v].push_back (u);
    }
    for (int i = 1; i <= m; i ++)
        scanf ("%d %d", &q[i].opt, &q[i].x);
    dfs1 (1, 0);
    dfs2 (1, 1);
    len = sqrt (m);
    num = 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 <= n; i ++)
        tim[i] = INF;
    for (int i = 1; i <= num; i ++){
        for (int j = l[i]; j <= r[i]; j ++){
            if (q[j].opt == 1)
                continue;
            if (q[j].opt == 2)
                ql = j;
            else{
                bool flag = 0;
                for (int k = max (l[i], ql + 1); k <= j - 1; k ++){
                    if (q[k].opt == 1 && get_dis(q[k].x, q[j].x) <= j - k){
                        flag = 1;
                        break;
                    }
                }
                if (ql < l[i] && tim[q[j].x] <= j)
                    flag = 1;
                if (flag)
                    printf ("wrxcsd\n");
                else
                    printf ("orzFsYo\n");
            }
        }
        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 (q[j].opt == 1 && tim[q[j].x] > j){
                tim[q[j].x] = j;
                Q.push (q[j].x);
            }
            while (! Q.empty ()){
                int now = Q.front ();
                if (tim[now] > j)
                    break;
                Q.pop ();
                for (int k = 0; k < G[now].size(); k ++){
                    int tmp = G[now][k];
                    if (tim[tmp] > tim[now] + 1){
                        tim[tmp] = tim[now] + 1;
                        Q.push (tmp);
                    }
                }
            }
        }
        while (! Q.empty ()){
            int now = Q.front ();
            Q.pop ();
            for (int k = 0; k < G[now].size(); k ++){
                int tmp = G[now][k];
                if (tim[tmp] > tim[now] + 1){
                    tim[tmp] = tim[now] + 1;
                    Q.push (tmp);
                }
            }
        }
    }
    return 0;
}

Thanks！