T3

C题考虑这样一个子问题：给定树上的点集 和询问点 ，判断是否存在 ，满足 ，其中 为两点路径的边数， 为当前时间戳， 为 加入的时间戳。

硬拆式子

其中 表示 到根路径经过的边数。

这个 不太好搞，但注意到 取 的公共祖先时，式子

在 处取得最大值，所以只需要维护所有公共祖先就可以了，也就是修改和查询直接操作所有祖先。

感性理解就是，如果在更早的祖先处绕了远路，肯定只会更合法。

对每个点维护初值 ，然后树链剖分+标记永久化线段树

复杂度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
    int ans=0;
    char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
vector<int> e[MAXN];
int dis[MAXN],fa[MAXN],siz[MAXN],son[MAXN];
void dfs(int u,int f)
{
    fa[u]=f,siz[u]=1;
    for (int i=0;i<(int)e[u].size();i++)
        if (e[u][i]!=f)
        {
            dis[e[u][i]]=dis[u]+1;
            dfs(e[u][i],u);
            siz[u]+=siz[e[u][i]];
            if (siz[e[u][i]]>siz[son[u]]) son[u]=e[u][i];
        }
}
int dfn[MAXN],pos[MAXN],tp[MAXN],tim;
void dfs(int u)
{
    pos[dfn[u]=++tim]=u;
    if (son[u]) tp[son[u]]=tp[u],dfs(son[u]);
    for (int i=0;i<(int)e[u].size();i++)
        if (e[u][i]!=fa[u]&&e[u][i]!=son[u])
            tp[e[u][i]]=e[u][i],dfs(e[u][i]);
}
#define lc p<<1
#define rc p<<1|1
int tag[MAXN<<2],mxd[MAXN<<2],ans[MAXN<<2],cl[MAXN<<2];
inline void update(int p){ans[p]=min(tag[p]-2*mxd[p],min(ans[lc],ans[rc]));}
inline void clear(int p){tag[p]=ans[p]=INF,cl[p]=1;}
inline void pushdown(int p){if (cl[p]) clear(lc),clear(rc),cl[p]=0;}
void build(int p,int l,int r)
{
    tag[p]=ans[p]=INF;
    if (l==r) return (void)(mxd[p]=dis[pos[l]]);
    int mid=(l+r)>>1;
    build(lc,l,mid),build(rc,mid+1,r);
    mxd[p]=max(mxd[lc],mxd[rc]);
}
void modify(int p,int l,int r,int ql,int qr,int v)
{
    if (ql<=l&&r<=qr) return (void)(ans[p]=min(ans[p],(tag[p]=min(tag[p],v))-2*mxd[p]));
    if (qr<l||r<ql) return;
    int mid=(l+r)>>1;
    pushdown(p);
    modify(lc,l,mid,ql,qr,v),modify(rc,mid+1,r,ql,qr,v);
    update(p);
}
int query(int p,int l,int r,int ql,int qr,int v)
{
    if (ql<=l&&r<=qr) return min(ans[p],v-2*mxd[p]);
    if (qr<l||r<ql) return INF;
    int mid=(l+r)>>1;
    pushdown(p);
    v=min(v,tag[p]);
    return min(query(lc,l,mid,ql,qr,v),query(rc,mid+1,r,ql,qr,v));
}
int n,m;
inline void modify(int x,int v){for (;x;x=fa[tp[x]]) modify(1,1,n,dfn[tp[x]],dfn[x],v);}
inline int query(int x,int ans=INF){for (;x;x=fa[tp[x]]) ans=min(ans,query(1,1,n,dfn[tp[x]],dfn[x],INF));return ans;}
int main()
{
    n=read(),m=read();
    for (int i=1;i<n;i++)
    {
        int u,v;
        u=read(),v=read();
        e[u].push_back(v),e[v].push_back(u);
    }
    dfs(1,0);
    dfs(tp[1]=1);
    build(1,1,n);
    for (int i=1;i<=m;i++)
    {
        int t,x;
        t=read(),x=read();
        if (t==1) modify(x,dis[x]+i);
        if (t==2) clear(1);
        if (t==3) puts(query(x)<=i-dis[x]? "wrxcsd":"orzFsYo");
    }
    return 0;
}