P4092 [HEOI2016/TJOI2016]树-树链剖分-点最近标记祖先

题目链接：https://www.luogu.com.cn/problem/P4116
题目大意：

思路：这题和https://blog.csdn.net/qq_21433411/article/details/103537858几乎一样。最近祖先，就是1-x这条链编号最大的标记点。把线段树改成维护区间编号最大的标记。

#include <bits/stdc++.h>
#define Rint register int
using namespace std;

#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)

const int maxn=1000005;
int n,m;
//见题意
int tot,head[maxn],nex[maxn],to[maxn], wt[maxn];
//链式前向星数组，w[]、wt[]初始点权数组
int a[maxn<<2];
//线段树数组
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
int res;
//查询答案

inline void add(int x,int y){//链式前向星加边
    to[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}
//-------------------------------------- 以下为线段树

inline void build(int rt,int l,int r){
    if(l==r){
        a[rt]=-1;
        return;
    }
    build(lson);
    build(rson);
    a[rt]=max(a[rt<<1], a[rt<<1|1]);
}

inline void update(int rt, int l, int r, int L, int R, int k){//实际上是一个单点修改
    if(L<=l&&r<=R){
        a[rt]=l;
    }
    else{
        if(L<=mid)update(lson,L,R,k);
        if(R>mid)update(rson,L,R,k);
        a[rt]=max(a[rt<<1], a[rt<<1|1]);
    }
}

inline void query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){ res=max(res, a[rt]);return;}
    else{
        if(L<=mid)query(lson,L,R);
        if(R>mid)query(rson,L,R);
    }
}

//-------------------------------------- 以上为线段树
inline int Q(int x, int y){
    res=-1;
    while(top[x]!=top[y]){//当两个点不在同一条链上
        if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
        query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
        x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    //直到两个点处于一条链上
    if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
    query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
    return res;
}

inline void U(int x, int k){
    update(1,1,n, id[x], id[x], k);
}

//-------------------------------------- 以下为模板
inline void dfs1(int x,int f,int deep){
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for(Rint i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];
    }
}

inline void dfs2(int x,int topf){
    id[x]=++cnt;
    wt[cnt]=x;
    top[x]=topf;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(Rint i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(Rint i=1;i<n;i++){
        int a,b;
        scanf("%d%d", &a, &b);
        add(a,b);add(b,a);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    U(1, 1);
    while(m--){
        char s[5];
        int b;
        scanf("%s%d", s, &b);
        if(s[0]=='C'){
            U(b, 1);//把b点的标记
        }
        else{
            int k=Q(1, b);
            printf("%d\n", wt[k]);
        }
    }
}