COCI2015/2016 Contest#4 D

题意：

​ 给出一个有 \(n\) 个节点的 \(k\) 叉树. \(k\) 叉树是指每个点最多有 \(k\) 个儿子的树(每一条边权值为1).每个节点的编号就是该节点加入树的顺序,每个节点从左往右添加到树中,节点 \(x\) 的深度增加当且仅当在它左边的每个节点都已经被填满了.(节点从1开始编号.)你现在要做的就是输出 \(Q\) 个询问的答案.每个询问 \((x,y)\) ,表示从 \(x\) 到 \(y\) 的最小步数。\((1\le N \le 10^{15})\)

---

​ 这道题不难，就是我被hack了。。。。

​ 所以在开篇补充一下，根据文中做法做的话在处理 \(k=1\) 的情况时会出现问题，所以当 \(k=1\) 时直接特判掉，此时 \((x,y)=\max(x,y)-\min(x,y)\)。

​ 我们看到这道题，首先联想到的肯定是 LCA。 但是注意到此题的数据范围，正常的倍增 LCA 是肯定过不了的。但是我们发现，根据题目的条件，他给的树一共只会有 \(\log(n)\) 层，那么，我们就可以省略倍增，直接模拟 倍增LCA 的过程，但是我们一次就爬一层，这样我们的时间复杂度就是 \(O(Q\times \log(N))\)。

​ 那么，我们目前的任务就是要在 \(O(1)\) 的时间内求出一个节点的父亲节点。同样的，我们还得根据一个节点的编号求出它所在的层数。

​ 首先我们来求层数，因为我们只需要求一次层数，后面在跳的时候可以手动把层数更新，这样避免重复调用求层数的函数。注意到，在题目所给的树中，第一层有 \(k^0\) 个节点，第二层有 \(k^1\) 个节点，我们可以发现规律，第 \(x\) 层就有 \(k^{x-1}\) 个节点，那么前 \(a\) 层就会有：\(\sum_{i-1}^{n} k^{i-1}\) 个节点。所以我们可以枚举层数，来进行判断，这样的时间复杂度是 \(O(\log(n))\)。

​ 那么对于父亲节点我们又怎么求呢？假设现在有一个点的编号为 \(x\)，而且他的层数为 \(d\)。那么我们先让求出 \(x-\sum_{i=1}^{d-1} k^{i-1}\) ，这个就是 \(x\) 在该层的编号，设这个值为 \(v\)。为了让每 \(k\) 个值除以 \(k\) 得到的商一致，我们将 \(v\)减去1。又因为每一个 \(d-1\) 层的节点在这一层都有 \(k\) 个儿子节点。我们算出 \((v-1)/k\) 这即是它父亲节点在上一层从左往右数的个数-1。综上所述，我们可以得到对于节点 \(x\) 他的父亲节点的编号为：

\[((x-\sum\limits_{i=1}^{d-1}{k^{i-1}}-1)/k)+1+\sum\limits_{i=1}^{d-2}{k^{i-1}} \]

​ 对于 \(\sum_{i=1}^{n}{k^{i-1}}\) 我们可以用数组预处理出来，到时候直接调用。

​ 那么接下来直接照着 LCA 的步骤去模拟就好了。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,q,up;
ll num[105];
ll solve_dep(ll x)
{
    ll p=1;
    ll dep=0;
    while(x>p)
    {
        x-=p;
        p*=k;
        ++dep;
    }
    return dep+1;
}
 
ll fa(ll x,ll dep)
{
    ll cnt=0,p=1,d;
    cnt=num[dep-1];
    d=x-cnt-1;
    d=d/k+1;
    cnt=num[dep-2];
    return cnt+d;
}
int main()
{
    scanf("%lld %lld %lld",&n,&k,&q);
    ll tmp=1;
    for(int i=1;i<=100;++i)
        num[i]=num[i-1]+tmp,tmp*=k;
    ll x,y,dep[2],ans=0;
    while(q--)
    {
        ans=0;
        scanf("%lld %lld",&x,&y);
        if(k==1)
        {
        	printf("%lld\n",max(x,y)-min(x,y));
        	continue;
		}
        if(x<y) swap(x,y);
        dep[0]=solve_dep(x),dep[1]=solve_dep(y);
        while(dep[0]>dep[1]) x=fa(x,dep[0]),dep[0]--,ans++;
        while(x!=y)
        {
            x=fa(x,dep[0]),y=fa(y,dep[1]);
            dep[0]--,dep[1]--;
            ans+=2;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

​ 文末再提一笔， \(k=1\) 的情况下在求父亲节点时会不断的除以1导致死循环，所以特判掉。