BZOJ_4551_[Tjoi2016&Heoi2016]树_树剖+线段树
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
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
Sample Output
1
2
2
1
2
2
1
标记的时候直接标该点在dfs序中的位置。
然后查询时查从根到这个点路径上点权最大值。
因为dfs序的性质，可以保证最大的一定离这个点最近。
然后树剖+线段树搞搞。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 200050
#define ls p<<1
#define rs p<<1|1
int c[N<<2],a[N],n,m,dep[N],fa[N],son[N],idx[N],top[N];
int head[N],to[N<<1],nxt[N<<1],cnt,siz[N],tot,sec,d[N];
char opt[10];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void dfs1(int x,int y) {
a[x]=++sec;
d[sec]=x;
dep[x]=dep[y]+1;
fa[x]=y;
siz[x]=1;
int i;
for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
void dfs2(int x,int t) {
top[x]=t; idx[x]=++tot;
int i;
if(son[x]) dfs2(son[x],t);
for(i=head[x];i;i=nxt[i]) if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
void update(int l,int r,int x,int v,int p) {
if(l==r) {
c[p]=v; return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,v,ls);
else update(mid+1,r,x,v,rs);
c[p]=max(c[ls],c[rs]);
}
int qmx(int l,int r,int x,int y,int p) {
if(x<=l&&y>=r) return c[p];
int mid=(l+r)>>1,re=0;
if(x<=mid) re=max(re,qmx(l,mid,x,y,ls));
if(y>mid) re=max(re,qmx(mid+1,r,x,y,rs));
return re;
}
int main() {
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<n;i++) {
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs1(1,0);
dfs2(1,1);
update(1,n,idx[1],1,1);
while(m--) {
scanf("%s%d",opt,&x);
if(opt[0]=='Q') {
y=1;
int ans=0;
while(top[x]!=top[y]) {
if(dep[top[x]]>dep[top[y]]) swap(x,y);
ans=max(ans,qmx(1,n,idx[top[y]],idx[y],1));
y=fa[top[y]];
}
if(dep[x]<dep[y]) swap(x,y);
ans=max(ans,qmx(1,n,idx[y],idx[x],1));
printf("%d\n",d[ans]);
}else {
update(1,n,idx[x],a[x],1);
}
}
}