题解 P4116 【Qtree3】

wxgwxg · 2018-01-19 11:24:44 · 题解

讲一下线段树维护的方法，维护dfs序区间中为黑点的最小的dfn值，白点赋值为inf，查询直接从下往上跳的时候查一下最小值就行了。

这样为什么是对的？

因为每次查询都是在一条链上，dfn最小就代表深度最小，也就是离1最近的点了。复杂度 qlogn.

效率也是相当不错的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline  int read()
{
    int k=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) k=k*10+c-'0';return f*k;
}
const int N=100055,inf=0x3f3f3f3f;
int n,m,tot,cnt,to[N<<1],nextt[N<<1],head[N],co[N],fa[N],dep[N],top[N],dfn[N],tr[N],mn[N<<2],size[N],son[N];
// tr[i]是dfn值为i的节点编号
void add(int a,int b)
{
    to[++tot]=b;
    nextt[tot]=head[a];
    head[a]=tot;
}
void dfs(int u,int f,int d)
{
    fa[u]=f;dep[u]=d;size[u]=1;
    for(int i=head[u];i;i=nextt[i])
    {
        if(to[i]==f) continue;
        dfs(to[i],u,d+1);size[u]+=size[to[i]];
        if(size[to[i]]>size[son[u]]) son[u]=to[i];
    }
} 
void dfs2(int u,int num)
{
    top[u]=num;dfn[u]=++cnt;tr[cnt]=u;
    if(!son[u]) return;
    dfs2(son[u],num);
    for(int i=head[u];i;i=nextt[i])
    {
        if(to[i]==fa[u]||to[i]==son[u]) continue;
        dfs2(to[i],to[i]);
    }
}
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
void pu(int k) {mn[k]=min(mn[k<<1],mn[k<<1|1]);}
void build(int k,int l,int r)
{
    if(l==r) {mn[k]=inf;return;}
    int mid=l+r>>1;
    build(lson);build(rson);
    pu(k);
}
void ch(int k,int l,int r,int x,int opt)
{
    if(l==r) {if(opt==1) mn[k]=l;else mn[k]=inf;return;}
    int mid=l+r>>1;
    if(x<=mid) ch(lson,x,opt);else ch(rson,x,opt);
    pu(k);
}
int query(int k,int l,int r,int a,int b)
{
    if(a<=l&&b>=r) return mn[k];
    int mid=l+r>>1,ans=inf;
    if(a<=mid) ans=min(ans,query(lson,a,b));
    if(b>mid ) ans=min(ans,query(rson,a,b));return ans; 
}
int query2(int x)
{
    int ans=inf;
    while(top[x]!=1)
    {
        ans=min(ans,query(1,1,n,dfn[top[x]],dfn[x]));x=fa[top[x]];
    }
    ans=min(ans,query(1,1,n,1,dfn[x]));return ans;
}
int main()
{
    int a,b;
    n=read();m=read();
    for(int i=1;i<n;i++)
    a=read(),b=read(),add(a,b),add(b,a);
    dfs(1,1,1);dfs2(1,1);build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        a=read();b=read();
        if(a==0) 
        {
            co[b]^=1;ch(1,1,n,dfn[b],co[b]);
        }
        else 
        {
            int k=query2(b);
            if(k==inf) puts("-1");
            else printf("%d\n",tr[k]);
        }
    }
    return 0;
}