P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

· · 题解

树剖求树上节点的 k 级祖先

题目传送门

闲话

我发现我有一个没 A 的蓝树剖

当树剖题做得比较多之后，简单的树剖还真能一眼出思路。

变量声明

思路

蒟蒻分类比较多（太菜，不会将情况合并）。

一、能到达

直接输出 to 并更新 now。

if(step>=dis1+dis2)wr(now=to),putchar(' ');

二、不能到达

蒟蒻怕错，将不能到达的情况又分成了两类：

  1. 向下跳

此时，从上向下跳 step 步就相当于从下向上跳 dis2-step 步。

else if(lca==now)
{
    now=tiao(to,dis2-step);
    wr(now),putchar(' ');
}
  1. 向上跳

还是为了防止出错，我又双叒叕分类了。

① 正巧跳到 lca：

直接输出 lca 并更新 now。

else if(dis1==step)wr(now=lca),putchar(' ');

② 在经过 lca 前不能走了：

now 向上跳 dis1 步。

else if(dis1>step)
{
    now=tiao(now,step);
    wr(now);putchar(' ');
}

③ 经过 lca 后停下：

总路程为 dis1+dis2，走过了 step，剩下了 dis1+dis2-step 步。to 向上跳 dis1+dis2-step 步。

else
{
    now=tiao(to,dis2-(step-dis1));
    wr(now);putchar(' ');
}

三、跳

思路中全是跳跳跳，那么到底怎么跳？

这题是什么？

对，树剖！

跳重链呗。

每次跳到重链的顶点的父节点，直到距离不够。

此时，当前节点和目标节点在一条重链上。

然后呢？

暴力跳？

树退化成链能让你当场去世

树剖有个美妙的性质，重链的时间戳是连续的。

而且深度也是连续的。

那么就有以下等式的推导：

dep_{now}-dep_{to}=dfn_{now}-dfn_{to}\\ -dep_{now}+dep_{to}+dfn_{now}=dfn_{to}\\ k=dep_{to}-dep_{now}\\ dfn_{to}=dfn_{now}-k\\ to=rnk[dfn_{to}] \end{array}

所以代码就是这样：

int tiao(int x,int k)
{
    while(1)
    {
        if(dep[x]-dep[top[x]]+1>k)break;
        k-=dep[x]-dep[top[x]]+1;
        x=fa[top[x]];
    }
    return rnk[dfn[x]-k];
}

全代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int re()
{
    int s=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        s=s*10+ch-48,ch=getchar();
    return s*f;
}
void wr(int s)
{
    if(s<0)putchar('-'),s=-s;
    if(s>9)wr(s/10);
    putchar(s%10+48);
}
const int inf=1e6+7;
int n,m;
int fir[inf],nex[inf<<1],poi[inf<<1],cnt;
void ins(int x,int y)
{
    nex[++cnt]=fir[x];
    poi[cnt]=y;
    fir[x]=cnt;
}
int fa[inf],dep[inf],siz[inf],son[inf];
void dfs1(int now,int from)
{
    siz[now]=1;fa[now]=from;
    dep[now]=dep[from]+1;
    for(int i=fir[now];i;i=nex[i])
    {
        int p=poi[i];
        if(p==from)continue;
        dfs1(p,now);
        siz[now]+=siz[p];
        if(siz[son[now]]<siz[p])
            son[now]=p;
    }
}
int top[inf],dfn[inf],rnk[inf],sum;
void dfs2(int now,int topn)
{
    top[now]=topn;
    dfn[now]=++sum;rnk[sum]=now;
    if(son[now]==0)return;
    dfs2(son[now],topn);
    for(int i=fir[now];i;i=nex[i])
    {
        int p=poi[i];
        if(p==fa[now]||p==son[now])
            continue;
        dfs2(p,p);
    }
}
int lca_(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int now;
int tiao(int x,int k)
{
    while(1)
    {
        if(dep[x]-dep[top[x]]+1>k)break;
        k-=dep[x]-dep[top[x]]+1;
        x=fa[top[x]];
    }
    return rnk[dfn[x]-k];
}
int main()
{
    n=re();now=re();m=re();
    for(int i=1;i<n;i++)
    {
        int u=re(),v=re();
        ins(u,v),ins(v,u);
    }
    dfs1(1,1);dfs2(1,1);
    for(int i=1;i<=m;i++)
    {
        int to=re(),step=re();
        int lca=lca_(now,to);
        int dis1=dep[now]-dep[lca],dis2=dep[to]-dep[lca];
        if(step>=dis1+dis2)wr(now=to),putchar(' ');
        else if(lca==now)
        {
            now=tiao(to,dis2-step);
            wr(now),putchar(' ');
        }
        else if(dis1==step)wr(now=lca),putchar(' ');
        else if(dis1>step)
        {
            now=tiao(now,step);
            wr(now);putchar(' ');
        }
        else
        {
            now=tiao(to,dis2-(step-dis1));
            wr(now);putchar(' ');
        }
    }
    return 0;
}

广告

树剖相关知识

My blog