LG-4116

给出 $N$ 个点的一棵树（$N-1$ 条边），节点有白有黑，初始全为白。

有两种操作：

0 i：改变某点的颜色（原来是黑的变白，原来是白的变黑）。

1 v：询问 $1$ 到 $v$ 的路径上的第一个黑点，若无，输出 $-1$。

思路

树上路径问题，所以很容易想到树剖。

考虑在 dfs 序上建线段树。

都是 $1$ 到某点的路径，而且求的是第一个黑点，也即 dfs 序最小的黑点。

于是考虑用线段树维护区间最小值，黑点就赋值为对应的 dfs 序，白点赋值为无穷大。

操作一单点修改，操作二查区间最小值即可。

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x7fffffff

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,q;

int head[N],tot=0;
struct graph{
    int v,next;
}edge[N<<1];
void add_edge(int u,int v) {edge[++tot].v=v,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}

int fa[N],depth[N],size[N],son[N],top[N],id[N],rk[N],cnt=0;
void dfs_first(int u) {
    size[u]=1;
    depth[u]=depth[fa[u]]+1;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs_first(v);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
void dfs_second(int u,int t) {
    if(!u) return ;
    top[u]=t;
    id[u]=++cnt;
    rk[cnt]=u;
    dfs_second(son[u],t);
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v!=fa[u]&&v!=son[u]) dfs_second(v,v);
    }
}

class SegmentTree{
  private:
    int minn[N<<2];
    #define m(x) minn[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        m(p)=min(m(ls),m(rs));
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            m(p)=INF;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int x) {
        if(l>x||r<x) return;
        if(l==r) {
            m(p)=(m(p)==INF?l:INF);
            return ;
        }
        modify(ls,l,mid,x),modify(rs,mid+1,r,x);
        update(p);
    }
    int ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return INF;
        if(l>=L&&r<=R) return m(p);
        return min(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
    }
}SMT;

int ask(int x,int y) {
    int tx=top[x],ty=top[y],ans=INF;
    while(tx!=ty) {
        if(depth[tx]>depth[ty]) {
            ans=min(ans,SMT.ask(1,1,n,id[tx],id[x]));
            x=fa[tx],tx=top[x];
        }
        else {
            ans=min(ans,SMT.ask(1,1,n,id[ty],id[y]));
            y=fa[ty],ty=top[y];
        }
    }
    if(id[x]<id[y]) ans=min(ans,SMT.ask(1,1,n,id[x],id[y]));
    else ans=min(ans,SMT.ask(1,1,n,id[y],id[x]));
    return ans;
}

void init() {
    dfs_first(1);
    dfs_second(1,1);
    SMT.build(1,1,n);
}

int main() {
    n=read(),q=read();
    for(int i=1;i<n;i++) {
        int u=read(),v=read();
        add(u,v);
    }    

    init();
    for(int i=1;i<=q;i++) {
        int op=read(),v=read();
        if(op==0) SMT.modify(1,1,n,id[v]);
        else {
            int ans=ask(1,v);
            printf("%d\n",ans==INF?-1:rk[ans]);
        }
    }
    system("pause");
    return 0;
}