牛半仙的妹子Tree（点分树+dp）

读完题目发现限制是和路径相关的，转化一下条件
对于修改和询问，如果，那么就会被影响到
考虑用点分树去维护，那么转化成了，移项（u,v来自不同的子树，表示）
然后注意到操作只有插入和清空，所以用对每个分治中心维护三个信息
分别表示，对应的属于哪个子树，和（和mx的v不能属于同一个子树），这里表示
更新操作就在点分树上往上跳，同时更新/清空当前分治中心的dp数组，然后先预处理一下数组即可
查询操作也在点分树上往上跳，如果存在一个（即）就说明会无视wrxcsd,否则不会无视orzFsYo
考场上傻fufu地用堆去维护最/次小值还写挂了
20.10.27upt：
和某巨巨讨论了一下发现不用维护次小值，因为()，所以即便最小值和询问来自同一个子树，它们的也满足条件（）就不用管它们是不是同一个子树啦

#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void Read(T &n){
    char ch; bool flag=false;
    while(!isdigit(ch=getchar())) if(ch=='-')flag=true;
    for(n=ch^48; isdigit(ch=getchar()); n=(n<<1)+(n<<3)+(ch^48));
    if(flag) n=-n;
}
#define no !

const int MAXN = 100005;
const int MAXK = 18;
const int inf = INT_MAX;

#define register 

int n, m;

struct _{
    int nxt, to;
    _(int nxt=0, int to=0):nxt(nxt),to(to){}
}edge[MAXN<<1];
int fst[MAXN], tot;

inline void Add_Edge(int f, int t){
    edge[++tot] = _(fst[f], t); fst[f] = tot;
    edge[++tot] = _(fst[t], f); fst[t] = tot;
}

int sz[MAXN];
bool vis[MAXN], Vis[MAXN];
int Weight, Center, Size;
void Get_Center(int x){
    vis[x] = true;
    int res = 0;
    sz[x] = 1;
    for(register int u=fst[x]; u; u=edge[u].nxt){
        int v=edge[u].to;
        if(Vis[v] or vis[v]) continue;
        Get_Center(v);
        sz[x] += sz[v];
        res = max(res,sz[v]);
    }
    res = max(res,Size-sz[x]);
    if(res < Weight)
        Weight = res,
        Center = x;
    vis[x] = false;
}

int f[MAXN];

int bel[MAXN][18], dis[MAXN][18];
int cur_dep, cur_bel, dep[MAXN];
void Get_Dis(int x){                         //预处理dis数组
    vis[x] = true;
    bel[x][cur_dep] = cur_bel;
    sz[x] = 1;
    for(register int u=fst[x]; u; u=edge[u].nxt){
        int v=edge[u].to;
        if(vis[v] or Vis[v]) continue;
        dis[v][cur_dep] = dis[x][cur_dep]+1;
        Get_Dis(v);
        sz[x] += sz[v];
    }
    vis[x] = false;
}

int fa[MAXN];                                
int Divide(int x, int depth){                //构建点分树 
    Size = sz[x]; Weight = Size+1; Get_Center(x);
    x = Center; Vis[x] = true;

    cur_dep = dep[x] = depth;
    for(register int u=fst[x]; u; u=edge[u].nxt){
        int v=edge[u].to;
        if(Vis[v]) continue;
        cur_bel = v;
        dis[v][cur_dep] = 1; Get_Dis(v);
    }

    for(register int u=fst[x]; u; u=edge[u].nxt){
        int v=edge[u].to;
        if(Vis[v]) continue;
        fa[Divide(v,depth+1)] = x;
    }

    return x;
}

inline void Add(int x, int opt, int T){      //更新，opt=1表示更新，opt=-1表示清空 
    int cur = x;
    for(register int i=dep[x]; ~i; i--){     //往上跳点分树 
        if(opt==1) f[cur] = min(f[cur],dis[x][i]+T);
        if(opt==-1) f[cur] = inf;
        cur = fa[cur];
    }
}

inline bool Query(int x, int T){            //查询 
    int cur = x;
    for(register int i=dep[x]; ~i; i--){    //往上跳点分树 
        if(T-dis[x][i]>=f[cur]) return false;
        cur = fa[cur];
    }
    return true;
}

struct upt{int x, T;}upd[MAXN]; int cnt;

inline void Clear(){
    for(register int i=1; i<=cnt; i++) Add(upd[i].x,-1,upd[i].T);
    cnt = 0;
}

int main(){
//    system("fc 3.txt 3.out");
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    Read(n); Read(m);
    for(register int i=1; i<n; i++){
        int f, t;
        Read(f); Read(t);
        Add_Edge(f,t);
    }
    memset(f,127,sizeof f);
    sz[1] = n; Divide(1,0);
    for(register int i=1; i<=m; i++){
        int opt, x;
        Read(opt); Read(x);
        if(opt==1) Add(x,1,i), upd[++cnt] = (upt){x,i};    //记录更新操作 
        if(opt==2) Clear();
        if(opt==3) puts(Query(x,i)?"orzFsYo":"wrxcsd");
    }
    return 0;
}