bzoj 4551

4551

思路：

　　乱搞；

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

#define maxm maxn<<1

#define maxtree maxn<<2

int n,head[maxn],E[maxm],V[maxm],cnt,m,deep[maxn],li[maxn],ri[maxn];

int val[maxtree],L[maxtree],R[maxtree],mid[maxtree],key[maxtree],tmp1,tmp2;

bool if_[maxtree];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void dfs(int now,int fa)

{

    deep[now]=deep[fa]+,li[now]=++cnt;

    for(int i=head[now];i;i=E[i])

    {

        if(V[i]==fa) continue;

        dfs(V[i],now);

    }

    ri[now]=cnt;

}

void build(int now,int l,int r)

{

    L[now]=l,R[now]=r;

    if(l==r)

    {

        if_[now]=true,val[now]=,key[now]=;

        return;

    }

    mid[now]=l+r>>;

    build(now<<,l,mid[now]);

    build(now<<|,mid[now]+,r);

}

void change(int now,int l,int r,int va,int ke)

{

    if(L[now]>=l&&R[now]<=r)

    {

        if(if_[now])

        {

            if(ke>key[now])key[now]=ke,val[now]=va;

        }

        else if_[now]=true,key[now]=ke,val[now]=va;

        return;

    }

    if(l<=mid[now]) change(now<<,l,r,va,ke);

    if(r>mid[now]) change(now<<|,l,r,va,ke);

}

void query(int now,int to)

{

    if(if_[now]&&key[now]>tmp2) tmp1=val[now],tmp2=key[now];

    if(L[now]==R[now]) return;

    if(to<=mid[now]) query(now<<,to);

    else query(now<<|,to);

}

int main()

{

    in(n),in(m);int u,v;

    for(int i=;i<n;i++)

    {

        in(u),in(v);

        E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;

        E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;

    }

    cnt=,dfs(,),build(,,n);

    char op[];

    for(int i=;i<=m;i++)

    {

        scanf("%s",op),in(u);

        if(op[]=='C') change(,li[u],ri[u],u,deep[u]);

        else tmp1=,tmp2=,query(,li[u]),printf("%d\n",tmp1);

    }

    return ;

}