BZOJ_4551_[Tjoi2016&Heoi2016]树

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

Sample Output

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
",d[ans]);
        }else {
            update(1,n,idx[x],a[x],1);
        }
    }
}