[Luogu 4092] HEOI/TJOI2016 树

<题目链接>

---

搜了树剖标签不知道怎么就跳出了个暴搜题啊！

管他既然做了就发上来吧…

有修改标签就向下搜并修改，遇到标签即停止。

这题是真的真的短。

#include <cstdio>

#include <queue>

using std::queue;

const int MAXN=100010;

bool flag[MAXN];

int n,q,cnt,head[MAXN],top[MAXN];

struct edge

{

    int nxt,to;

    edge(int nxt=0,int to=0):nxt(nxt),to(to){}

}e[MAXN<<1];

void AddEdge(int u,int v)

{

    e[++cnt]=edge(head[u],v);

    head[u]=cnt;

}

void PushDown(int x)

{

    queue<int> q;

    q.push(x),flag[x]=top[x]=x;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u],v;i;i=e[i].nxt)

            if(!flag[v=e[i].to] && x^top[v])

                q.push(v),top[v]=x;

    }

}

int main(int argc,char *argv[])

{

    scanf("%d %d",&n,&q);

    for(int i=1,x,y;i<n;++i)

    {

        scanf("%d %d",&x,&y);

        AddEdge(x,y),top[i]=1;

    }

    top[n]=1;

    for(int i=1,x;i<=q;++i)

    {

        char c;

        scanf("\n%c %d",&c,&x);

        if(c=='C')

            PushDown(x);

        else

            printf("%d\n",top[x]);

    }

    return 0;

}

谢谢阅读。