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\n",d[ans]);

        }else {

            update(1,n,idx[x],a[x],1);

        }

    }

}

秒客网