欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P4116 Qtree3 树链剖分-路径上第一个标记

程序员文章站 2024-02-14 12:38:28
...

题目链接:https://www.luogu.com.cn/problem/P4116
题目大意:
P4116 Qtree3 树链剖分-路径上第一个标记
轻重链剖分后,新的标号仍然满足深度d[u]>d[v],那么id[u]>d[v]。所以现在就可以在线段树上维护区间第一个标记。和单点修改标记。

#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]=n+1;
        return;
    }
    build(lson);
    build(rson);
    a[rt]=min(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){
        if(a[rt]==l){
            a[rt]=n+1;
        }
        else{
            a[rt]=l;
        }
    }
    else{
        if(L<=mid)update(lson,L,R,k);
        if(R>mid)update(rson,L,R,k);
        a[rt]=min(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=min(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=n+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);
    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        if(a==0){
            U(b, 1);//把b点的颜色取反
        }
        else{
            int k=Q(1, b);
            if(k==n+1){
                printf("-1\n");
            }
            else{
                printf("%d\n", wt[k]);
            }
        }
    }
}
相关标签: 树链剖分