[bzoj4551][Tjoi2016][Heoi2016]树

Description

在\(2016\)年，佳媛姐姐刚刚学习了树，非常开心。

现在她想解决这样一个问题：给定一颗有根树（根为\(1\)），有以下两种操作：

\(1.\) 标记操作：对某个结点打上标记（在最开始，只有结点\(1\)有标记，其他结点均无标记，而且对于某个结点，可以打多次标记）;

$2. $询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）.

你能帮帮她吗?

Input

输入第一行两个正整数\(N,Q\),分别表示节点个数和操作次数.

接下来\(N-1\)行，每行两个正整数\(u,v\),表示\(u\)到\(v\)有一条有向边.

接下来\(Q\)行，形如\("oper\;num".oper\)为\("C"\)时,表示这是一个标记操作;

\(oper\)为\("Q"\)时,表示这是一个询问操作.

Output

输出一个正整数，表示结果.

Sample Input

5 5 
1 2 
1 3 
2 4 
2 5 
Q 2 
C 2 
Q 2 
Q 5 
Q 3

Sample Output

1 
2 
2 
1

HINT

\(1\;\leq\;N,Q\;\leq\;10^5,1\;\leq\;u,v\;\leq\;n\)

Solution

正难则反,对于所有操作逆序离线处理.

先记录每个节点被打过几次标记,预处理出每个节点最后时刻最近的打了标记的祖先.

从后往前消除标记,如果当前点的标记被消除完,则这个点最近的打了标记的祖先为它父亲最近的打了标记的祖先,并查集可实现.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
using namespace std;
struct graph{
    int nxt,to;
}e[N<<1];
struct quest{
    int t,x;
}b[N];
int a[N],f[N],g[N],fa[N],ans[N],n,m,q,t,x,cnt;
stack s;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline int rc(){
    char c=getchar();
    while(c!='Q'&&c!='C') c=getchar();
    if(c=='C') return 1;
    return 2;
}
inline void addedge(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void dfs(int u){
    fa[u]=f[u]=1;s.push(u);
    while(!s.empty()){
        u=s.top();s.pop();
        for(int i=g[u];i;i=e[i].nxt)
            if(fa[u]!=e[i].to){
                fa[e[i].to]=u;s.push(e[i].to);
                if(!a[e[i].to]) f[e[i].to]=f[u];
                else f[e[i].to]=e[i].to;
            }
    }
}
inline int gf(int k){
    if(f[k]==k) return k;
    return f[k]=gf(f[k]);
}
inline void init(){
    n=read();q=read();
    for(int i=1,j,k;i