题解：P4116 Qtree3

· · 题解

传送门

一个很暴力的算法。

首先打出基础的树链剖分，线段树直接维护一段 dfs 序区间内黑点的个数，如果个数大于 0 就说明这一段有黑点。

在进行查询的时候，要对查询进行一定的更改。首先要找到第一个黑点可以转化成找到 dfs 序最小的黑点，那么这个点所在的链的链底一定是所有黑点所在的链的链底中 dfs 序最小的。于是在查询 1 到 x 的路径上第一个黑点的时候，就用 s 把其中的含有黑点的链中 dfs 序最小的链底存起来，如果没有找到黑点函数返回 -1。

接下来直接暴力跑 s 所在的链找黑点肯定是不行的，于是这里用 l 记录 s 这条链的链顶的 dfs 序，用 r 记录 s 的 dfs 序。记 block=\sqrt n，然后循环每次查询 l 到 l+block-1 这段 dfs 序中是否有黑点，如果有就暴力遍历 l 到 l+block-1 这段 dfs 序查找第一个黑点，否则 l 变为 l+block，若 l+block-1>r 则退出循环，并暴力遍历 l 到 r 找第一个黑点。

CODE:

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
#define ll long long
using namespace std;
int n,q;
vector<int> g[100010];
int tot=0,dy[100010];
struct tree
{
    int fa,son,dfn,top,size,h;
}tr[100010];
int xds[400010];
int a[100010];
inline void dfs1(int k)
{
    tr[k].size=1;
    for(register int i=0;i<g[k].size();i++)
    {
        int x=g[k][i];
        if(x==tr[k].fa) continue;
        tr[x].fa=k,tr[x].h=tr[k].h+1,dfs1(x),tr[k].size+=tr[x].size;
        if(!tr[k].son) tr[k].son=x;
        else if(tr[tr[k].son].size<tr[x].size) tr[k].son=x;
    }
}
inline void dfs2(int k,int tp)
{
    tr[k].top=tp,tot++,tr[k].dfn=tot,dy[tot]=k;
    if(!tr[k].son) return;
    dfs2(tr[k].son,tp);
    for(register int i=0;i<g[k].size();i++)
    {
        int x=g[k][i];
        if(x==tr[k].fa) continue;
        if(x!=tr[k].son) dfs2(x,x);
    }
}
inline void change(int l,int r,int pos,int k)
{
    if(l==r)
    {
        xds[k]^=1;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) change(l,mid,pos,lc);
    else change(mid+1,r,pos,rc);
    xds[k]=xds[lc]+xds[rc];
}
inline int query(int l,int r,int ql,int qr,int k)
{
    if(ql<=l&&r<=qr) return xds[k];
    int sum=0,mid=(l+r)>>1;
    if(ql<=mid) sum+=query(l,mid,ql,qr,lc);
    if(mid<qr) sum+=query(mid+1,r,ql,qr,rc);
    return sum;
}
inline int qulca(int x)
{
    int sum=n+1;
    while(1)
    {
        int tx=tr[x].top;
        if(tx==1) break;
        if(query(1,n,tr[tx].dfn,tr[x].dfn,1)) sum=min(sum,tr[x].dfn);
        x=tr[tx].fa;
    }
    if(query(1,n,1,tr[x].dfn,1)) sum=min(sum,tr[x].dfn);
    if(sum==n+1) return -1;
    sum=dy[sum];
    int block=sqrt(n);
    int l=tr[tr[sum].top].dfn,r=tr[sum].dfn;
    if(l+block-1>=r)
        for(register int i=l;i<=r;i++)
            if(a[dy[i]])
                return dy[i];
    while(l+block-1<r)
    {
        if(query(1,n,l,l+block-1,1))
            for(register int i=l;i<=l+block-1;i++)
                if(a[dy[i]])
                    return dy[i];
        l+=block;
    }
    for(register int i=l;i<=r;i++)
        if(a[dy[i]])
            return dy[i];
    return -1;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(register int i=1;i<=n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs1(1),dfs2(1,1);
    while(q--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(!op) change(1,n,tr[x].dfn,1),a[x]^=1;
        if(op) printf("%d\n",qulca(x));
    }
    return 0;
}