题解 P4116 【Qtree3】

yu__xuan · 2020-05-10 14:53:53 · 题解

题目

P4116 Qtree3

思路

树链剖分。1 到 v 的路径上的第一个黑点就是 1 到 v 路径上 dfs 序最小的黑点。我们只需要把黑点的权值赋成该点的 dfs 序，白点的权值赋成无穷大，就把查询 1 到 v 的路径上的第一个黑点转化成了查询1 到 v 的路径上的最小值的问题了。如果最小值等于无穷大那么输出 -1，否则输出最小值（dfs 序）对应的点的编号。

Code

#include<cstdio>
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#define MAXN 100001
#define inf 2147483647

inline void read(int &T) {
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    T=f?-x:x;
}

int n,q,dfn[MAXN],pre[MAXN],size[MAXN];

int min(int a,int b) {return a<b?a:b;}

namespace Seg {
    #define lson now<<1
    #define rson now<<1|1
    struct Node {
        int l,r,w;
    }tree[MAXN<<2];
    void build(int l,int r,int now) {
        tree[now].l=l,tree[now].r=r;
        if(tree[now].l==tree[now].r) {
            tree[now].w=inf;return;
        }
        int mid=(tree[now].l+tree[now].r)>>1;
        build(l,mid,lson),build(mid+1,r,rson);
        tree[now].w=min(tree[lson].w,tree[rson].w);
    }
    void update(int x,int now) {
        if(tree[now].l==tree[now].r) {
            if(tree[now].w!=inf) tree[now].w=inf;
            else tree[now].w=tree[now].l;
            return;
        }
        int mid=(tree[now].l+tree[now].r)>>1;
        if(x<=mid) update(x,lson);
        else update(x,rson);
        tree[now].w=min(tree[lson].w,tree[rson].w);
    }
    int query(int x,int y,int now) {
        if(tree[now].l>=x&&tree[now].r<=y) return tree[now].w;
        int mid=(tree[now].l+tree[now].r)>>1,ans=inf;
        if(x<=mid) ans=min(ans,query(x,y,lson));
        if(y>mid) ans=min(ans,query(x,y,rson));
        return ans;
    }
}

namespace Cut {
    int cnt,pthn,head[MAXN],dep[MAXN];
    int fa[MAXN],son[MAXN],top[MAXN];
    struct Edge {
        int next,to;
    }pth[MAXN<<1];
    void add(int from,int to) {
        pth[++pthn].to=to,pth[pthn].next=head[from];
        head[from]=pthn;
    }
    void dfs1(int u,int father) {
        fa[u]=father,dep[u]=dep[father]+1,size[u]=1;
        for(int i=head[u];i;i=pth[i].next) {
            int x=pth[i].to;
            if(x!=father) {
                dfs1(x,u),size[u]+=size[x];
                if(size[son[u]]<size[x]) son[u]=x;
            }
        }
    }
    void dfs2(int u,int tp) {
        top[u]=tp,dfn[u]=++cnt,pre[cnt]=u;
        if(son[u]) dfs2(son[u],tp);
        for(int i=head[u];i;i=pth[i].next) {
            int x=pth[i].to;
            if(x!=fa[u]&&x!=son[u]) dfs2(x,x);
        }
    }
    int ask(int x,int y) {
        int ans=inf;
        while(top[x]!=top[y]) {
            if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
            ans=min(ans,Seg::query(dfn[top[x]],dfn[x],1));
            x=fa[top[x]];
        }
        if(dep[x]>dep[y]) std::swap(x,y);
        ans=min(ans,Seg::query(dfn[x],dfn[y],1));
        if(ans==inf) return -1;
        return ans;
    }
}

int main() {
    read(n),read(q);
    for(int i=1,u,v;i<n;++i) {
        read(u),read(v);
        Cut::add(u,v),Cut::add(v,u);
    }
    Cut::dfs1(1,1),Cut::dfs2(1,1),Seg::build(1,n,1);
    for(int i=1,opt,x;i<=q;++i) {
        read(opt),read(x);
        if(opt==0) Seg::update(dfn[x],1);
        else {
            int ccc=Cut::ask(1,x);
            if(ccc==-1) puts("-1");
            else printf("%d\n",pre[ccc]);
        }
    }
    return 0;
}