Description
在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下
两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个
结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖
先）你能帮帮他吗?
Input
输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v
有一条有向边接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询
问操作对于每次询问操作，1 ≤ N, Q ≤ 100000。
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
题解:感觉树链剖分的思路还是很好想的,一个点的祖宗肯定在它到根的路径里,我们可以令每个打标记的点权值为一,对于每条完整的链统计区间和,如果大于零,说明这段区间上至少有一个打了标记的点,对于这段区间,求出后一段的前缀和,如果是0,搜索前一段,否则搜索后一段.这是一种二分的思路.
代码如下:
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson root<<1
#define rson root<<1|1
using namespace std; struct node
{
int sum,l,r;
}tr[];
int deep[],fa[],size[],son[],w[],iid[],id[],c[],top[],cnt;
vector<int> g[]; void push_up(int root)
{
tr[root].sum=tr[lson].sum+tr[rson].sum;
} void build(int root,int l,int r)
{
if(l==r)
{
tr[root].l=l;
tr[root].r=r;
tr[root].sum=w[l];
return ;
}
tr[root].l=l;
tr[root].r=r;
int mid=(l+r)>>;
build(lson,l,mid);
build(rson,mid+,r);
push_up(root);
} void update(int root,int x,int val)
{
if(x==tr[root].l&&x==tr[root].r)
{
tr[root].sum=val;
return ;
}
int mid=(tr[root].l+tr[root].r)>>;
if(x<=mid)
{
update(lson,x,val);
}
else
{
update(rson,x,val);
}
push_up(root);
} int query(int root,int l,int r)
{
if(l==tr[root].l&&tr[root].r==r)
{
return tr[root].sum;
}
int mid=(tr[root].l+tr[root].r)>>;
if(l>mid)
{
return query(rson,l,r);
}
else
{
if(r<=mid)
{
return query(lson,l,r);
}
}
return query(lson,l,mid)+query(rson,mid+,r);
} void dfs1(int now,int f,int dep)
{
deep[now]=dep;
fa[now]=f;
size[now]=;
int maxson=-;
for(int i=;i<g[now].size();i++)
{
if(g[now][i]==f)
{
continue;
}
dfs1(g[now][i],now,dep+);
size[now]+=size[g[now][i]];
if(maxson<size[g[now][i]])
{
maxson=size[g[now][i]];
son[now]=g[now][i];
}
}
} void dfs2(int now,int topf)
{
id[now]=++cnt;
iid[cnt]=now;
w[cnt]=c[now];
top[now]=topf;
if(!son[now])
{
return;
}
dfs2(son[now],topf);
for(int i=;i<g[now].size();i++)
{
if(g[now][i]==son[now]||g[now][i]==fa[now])
{
continue;
}
dfs2(g[now][i],g[now][i]);
}
} int check(int l,int r)
{
if(l==r)
{
return l;
}
int mid=(l+r)>>;
int tmp=query(,mid+,r);
if(tmp)
{
return check(mid+,r);
}
else
{
return check(l,mid);
}
} int path_query(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
{
swap(x,y);
}
int tmp=query(,id[top[x]],id[x]);
if(!tmp)
{
x=fa[top[x]];
}
else
{
return check(id[top[x]],id[x]);
}
}
if(deep[x]>deep[y])
{
swap(x,y);
}
return check(id[x],id[y]);
} int main()
{
int n,m,vv;
scanf("%d%d",&n,&m);
for(int i=;i<=n-;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
c[]=;
dfs1(,,);
dfs2(,);
build(,,n);
char c;
for(int i=;i<=m;i++)
{
scanf("\n%c %d",&c,&vv);
if(c=='C')
{
update(,id[vv],);
}
if(c=='Q')
{
printf("%d\n",iid[path_query(,vv)]);
}
}
}