题解：CF2223C Zhily and Signpost

· · 题解

吐槽

exgcd 是什么？我不会写啊！

树剖又是啥？我怎么完全没学过！

DFS 又是啥？俺寻思俺也妹写 DFS 啊？

来介绍一个以上三者都没用到的做法。

正文

当然首先还是要往同余方程组上想的，能走到某个点 x 的时间 t 一定是满足若干个同余方程的限制的，每个同余方程的模数是对应某个点父亲的儿子个数。所以最后走到 x 时可以合并成一个模数为根到 x 路径上儿子个数 \operatorname{LCM} 的同余方程。我们记根到 x 路径上儿子个数的 \operatorname{LCM} 为 L_{x}（为和后面的代码保持一致这里把 x 的儿子个数也算进 L_x 里），能走到 x 的对应合并后同余方程的模数就是 L_{f_x}（f_x 表示 x 的父亲）。

那么在往下走合并同余方程的过程中，模数（也就是 L_x）当然是可能会爆的。但由于我们只需考虑 t\le 10^{18} 的情况，所以这时可以认为走到当前点 x 的时刻是固定的。后续就不需要再考虑同余方程合并的事情，直接模拟即可。

此外，如果 L_x=L_{f_x}，那么在走到 x 时 t \bmod L_x 的值已经固定，所以只要走到了 x 就一定会走到 x 的某个确定的儿子 y，这里可以想办法预处理合并。

这时就能发现，如果能把所有刚才描述的“如果能到 x，就一定会走到 y”这个玩意用并查集提前合并一下，那么每次询问时就可以直接暴力往下跳。因为当 L_x 发生变化时对应值至少 \times 2，所以最多只会暴力跳 \log 次模数就会爆掉。后面可以直接模拟记忆化或者直接预处理。

到这里其实就已经做完了，因为可以通过 DFS 和 exgcd 把每个位置对应的同余方程都求出来，然后就能实现刚刚的预处理。

但是我不会写 exgcd 啊！

既然模数爆掉的情况可以直接模拟并记忆化对应结果，那模数不变的情况好像也可以记忆化啊！

每次询问的时候直接暴力模拟，等到路上遇到模数不变的情况时再利用并查集合并。这样同样也能实现对应预处理合并的效果。

最后在每次询问的时候直接不断暴力找儿子并 Find(x) 即可。

代码实现

对于模数爆掉的情况，可以直接将 L_x 设为 inf，把后面的合并过程当做前面模数不变的情况处理。

这里如果不开 __int128 的话要注意判断是否爆掉的方式，主播一开始写的是 if(inf/k>L[i])L[i]=inf; 直接就挂麻了调了老半天。

其实是可以把并查集省掉的。因为实际上每个点只会被合并一次，所以可以记一个 vis 数组，当每次询问结束后发现 vis 更新的时直接暴力往回合并即可。

#include<bits/stdc++.h>
using namespace std;
#define N 500050
#define LL long long
int T,n,q,f[N],nxt[N];
LL m,dis[N],L[N];
vector<int>d[N];
const LL inf=5e18;
int Find(int x){return nxt[x]==x?x:nxt[x]=Find(nxt[x]);}
void init()
{
    L[0]=1;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)d[i].clear(),nxt[i]=i;
    for(int i=2;i<=n;i++){
        scanf("%d",&f[i]);
        d[f[i]].push_back(i);
    }
    L[1]=d[1].size();
    for(int i=2;i<=n;i++){
        scanf("%lld",&dis[i]);
        dis[i]+=dis[f[i]];
        if(d[i].empty())continue;
        L[i]=d[i].size();
        LL k=L[f[i]]/__gcd(L[f[i]],L[i]);
        if(k>inf/L[i])L[i]=inf;
        else L[i]*=k;
    }
    while(q--){
        scanf("%lld",&m);
        int x=1;
        while(!d[x].empty()){
            if(L[x]==L[f[x]])nxt[x]=d[x][(m+dis[x])%d[x].size()];
            x=d[x][(m+dis[x])%d[x].size()];
            x=Find(x);
        }
        printf("%d%c",x,q?' ':'\n');
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)init();
}

交上去之后也是喜提最短解啊！（虽然现在已经不是了）