题目描述

给⼀棵树，现在有两种操作：

  1. 标记某⼀个节点；

  2. 找到路径 $a$ 至 $b$ 中在第 $y$ 次操作到当前操作之间没有被标记的第 $k$ 个节点。

保证每个节点只会被标记一次。

完整题面

思路

首先用可持久化线段树维护树剖，对于修改操作直接修改即可，对于查询，直接在树剖上跳，如果未标记节点小于 $k$ 输出 -1，否则输出答案。

实现

这道题个人认为最大的难点是在代码实现上，以及本人代码实现较差。

首先进行树剖，维护使用可持久化线段树。

对于修改操作，直接根据 dfs 序修改即可。

对于查询操作，首先分为两部分：从 $a$ 至 $lca$ 的部分和从 $lca$ 至 $b$ 的部分，特判 $a$ 或 $b$ 为 $lca$ 的情况。

对于每个被剖出来的区间，我们可以放进一个容器里，如果是下至上就可以用队列，如果上至下就可以用栈，当然用 vector 然后再 reserve 一下也可以。

然后就判断第 $k$ 个没打标记的在哪个区间内。

有两种方法可以判断第 $k$ 个在区间中的具体位置：

  1. 在线段树上特定区间二分，能写，但是个人认为容易写挂；

  2. 直接二分位置，然后判断是否合法。

注意此时要根据上行或下行判断是区间左边第 $k$ 个还是区间右边第 $k$ 个。

以及由于是被分开的询问还是开区间，使用倍增找出 $lca$ 的儿子。

具体实现细节在代码中。

时间复杂度 $O(n\log^2n)$。

喜闻乐见的代码

#include<assert.h>
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
struct Persistent_Segment_Tree//可持久化线段树，不用多说
{
    int cnt;
    struct sss
    {
        int l,r,sum;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define sum(x) tree[x].sum
    }tree[5000005];
    int build(int l,int r)
    {
        int root=++cnt;
        if(l==r)return root;
        int mid=(l+r)>>1;
        l(root)=build(l,mid);
        r(root)=build(mid+1,r);
        return root;
    }
    int change(int x,int l,int r,int p)
    {
        int root=++cnt;
        tree[root]=tree[x];
        if(l==r)return sum(root)=1,root;
        int mid=(l+r)>>1;
        if(p<=mid)l(root)=change(l(root),l,mid,p);
        else r(root)=change(r(root),mid+1,r,p);
        sum(root)=sum(l(root))+sum(r(root));
        return root;
    }
    int ask(int x,int y,int L,int R,int l,int r)
    {
        if(l<=L&&R<=r)return sum(y)-sum(x);
        int mid=(L+R)>>1,ans=0;
        if(l<=mid)ans+=ask(l(x),l(y),L,mid,l,r);
        if(mid<r)ans+=ask(r(x),r(y),mid+1,R,l,r);
        return ans;
    }
}T1;
struct sss
{
    int q,w,nxt;
}a[1000005];
int head[1000005],cnt,dfn[1000005],f[1000005],son[1000005],s[1000005],top[1000005],d[1000005];
int n,root[1000005],c[1000005],T,low[1000005],P[1000005][25];
void adde(int q,int w)
{
    a[++cnt].q=q;
    a[cnt].w=w;
    a[cnt].nxt=head[q];
    head[q]=cnt;
}
void dfs1(int x,int fa)//树剖
{
    s[x]=1;
    f[x]=fa;
    d[x]=d[fa]+1;
    P[x][0]=fa;
    for(int i=1;i<=20;i++)P[x][i]=P[P[x][i-1]][i-1];//倍增
    int id=0;
    for(int i=head[x];i;i=a[i].nxt)
    {
        if(fa^a[i].w)
        {
            dfs1(a[i].w,x);
            s[x]+=a[i].w;
            if(s[id]<s[a[i].w])id=a[i].w;
        }
    }
    son[x]=id;
}
void dfs2(int x,int tp)//树剖
{
    dfn[x]=++cnt;
    low[cnt]=x;
    top[x]=tp;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];i;i=a[i].nxt)if(f[x]!=a[i].w&&a[i].w!=son[x])dfs2(a[i].w,a[i].w);
}
void change(int x,int T){c[x]=1;root[T]=T1.change(root[T-1],1,n,dfn[x]);}
int LCA(int x,int y)//树剖求LCA
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]])swap(x,y);
        x=f[top[x]];
    }
    if(d[x]<d[y])swap(x,y);
    return y;
}
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
stack<pii>S;
queue<pii>q;
bool Farmer;
void Push(pii a){if(Farmer)q.push(a);else S.push(a);}
void Pop(){if(Farmer)q.pop();else S.pop();}
pii Front(){if(Farmer)return q.front();return S.top();}
pii Top(){if(Farmer)return q.front();return S.top();}
void Clear(){while(S.size())S.pop();while(q.size())q.pop();}
bool Empty(){if(Farmer)return q.empty();return S.empty();}
//这里是维护被剖出来的区间顺序，通过Farmer来决定是栈还是队列
int Um_nik(int L,int R,int k,int t)//二分
{
    int o=L-1,l=L-o,r=R-o,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        int u;//计算满足要求的节点数量，记得判断上行或下行
        if(Farmer)u=d[low[R]]-d[low[mid+o]]+1-T1.ask(root[t],root[T],1,n,mid+o,R);
        else u=d[low[mid+o]]-d[low[L]]+1-T1.ask(root[t],root[T],1,n,L,mid+o);
        if(u>=k)
        {
            if(Farmer)l=mid+1;
            else r=mid-1;
            ans=mid+o;
        }
        else Farmer?r=mid-1:l=mid+1;
    }
    return low[ans];//由于是通过 dfs 序二分，返回要转回原来编号
}
int Ask(int x,int y,int t,int k)
{
    if(k>0)Farmer=1;//Farmer 为 1 上行，否则下行
    else Farmer=0,k=-k;
    Clear();
    if(!y)y=1;//特判 y 为 0
    else
    {
        int Y=x;
        for(int i=20;i>=0;i--)if(d[P[Y][i]]>d[y])Y=P[Y][i];
        y=Y;//查找儿子
    }
    x=f[x];
    if(d[x]<d[y])return -1e9;
    int num=0;
    while(top[x]!=top[y])//树剖
    {
        if(d[x]<d[y])swap(x,y);
        num+=d[x]-d[top[x]]+1-T1.ask(root[t],root[T],1,n,dfn[top[x]],dfn[x]);
        Push(mp(dfn[top[x]],dfn[x]));//将剖下来的区间放入容器中
        x=f[top[x]];
    }
    if(d[x]<d[y])swap(x,y);
    num+=d[x]-d[y]+1-T1.ask(root[t],root[T],1,n,dfn[y],dfn[x]);
    Push(mp(dfn[y],dfn[x]));
    if(num<abs(k))return -num;//如果节点数量不够直接用负数返回节点数
    while(!Empty())
    {
        pii x=Front();
        Pop();
        int o=d[low[x.second]]-d[low[x.first]]+1-T1.ask(root[t],root[T],1,n,x.first,x.second);
        if(o>=k)return Um_nik(x.first,x.second,k,t);//查找第k大
        k-=o;
    }
    return -1e9;
}
int ask(int x,int y,int t,int k)
{
    int o=1;
    if(d[x]<d[y])swap(x,y),o=-1;
    int lca=LCA(x,y);
    if(lca==y)return Ask(x,y,t,k*o);//特判y为lca
    int p=Ask(o+1?x:y,f[lca],t,k);
    if(p>0)return p;//如果p为正数则找到了解
    k+=p;
    p=Ask(o+1?y:x,lca,t,-k);//用负数表示上下行
    return p;
}
int Q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int q;
        scanf("%d",&q);
        if(q)adde(i,q),adde(q,i);
    }
    cnt=0;
    root[0]=T1.build(1,n);
    dfs1(1,0);
    dfs2(1,1);//建树
    scanf("%d",&Q);
    while(Q--)
    {
        int op,x,y,k,t;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            change(x,++T);
        }
        else
        {
            root[T+1]=root[T];//新建版本
            T++;
            scanf("%d%d%d%d",&x,&y,&k,&t);
            int ans=ask(x,y,t,k);//ans为正为有解
            printf("%d\n",ans<=0?-1:ans);
        }
    }
}