题解：CF2223C Zhily and Signpost

· · 题解

一个非常自然的做法是，对于每个点 u，到达 u 的充要条件可以写作 X\bmod a_u=b_u，其中 X 是初始时间，a_u 是 u 到祖先路径上的儿子度数的 \rm lcm。

很容易用 excrt 求出所有 a,b，但是然后你发现做不了了。

考虑优化。这种模拟操作题有一个方向是性质优化模拟，我们来找。你发现 \rm lcm 的值至多变化 \log V 次就会达到 10^{18}，再往上就可以视作 +\infty。这个有什么用呢？

考虑过程中先后经过的 u,v 两点，\rm lcm 为祖先儿子数量的 \rm lcm，记 d 为儿子数量，如果 d_v\mid{\rm lcm}_u，也即 d_v 如果不是改变 \rm lcm 的关键点，那么 v 的下一步是个定点。

为什么？因为从 u 走下来的条件是 \bmod\ {\rm lcm}_u 为一定值，而 d_v 整除它，那么到达 v 的时候对 d_v 的余数也是定值！

另一种情形，如果 \rm lcm 大于 10^{18} 了，虽然不是同一原理，但是一样的效果：下一步必然是定点。

于是我们直接模拟。模拟过程中进行如下记忆化：to_i 表示 i 极长的定点链尾即可。如果 to_i\neq i 就直接跳过去（之前处理过），否则先一步一步走 nxt_i，把 to_i 处理完，令 to_i=to_{nxt_i} 即可。每次询问至多暴力跳 \log 次。

代码非常好写，也非常好懂，也根本不需要树剖或者 excrt。复杂度 O((n+q)\log V)。

#include<bits/stdc++.h>
using namespace std;

#define int __int128
#define MAXN 500005

const int Lim = (int)1e18;

int n,q,to[MAXN],Lcm[MAXN],dep[MAXN];
int f[MAXN],l[MAXN],deg[MAXN];

vector<int> E[MAXN];

inline int read(){
    int x = 0; char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = x * 10 + ch - 48,ch = getchar();
    return x;
} 

int gcd( int a , int b ){ return b ? gcd( b , a % b ) : a; }

void init( int x , int lc ){
    Lcm[x] = lc,dep[x] = dep[f[x]] + l[x];
    for( int i = 0 ; i < deg[x] ; i ++ ){
        int v = E[x][i];
        if( lc == Lim + 1 ) init( v , Lim + 1 );
        else if( lc % deg[x] == 0 ) init( v , lc );
        else{
            int g = gcd( lc , deg[x] );
            int lcm = lc / g * deg[x];
            if( lcm <= Lim ) init( v , lcm );
            else init( v , Lim + 1 );
        }
    }
}

int get_ans( int x , int now ){
    if( !E[x].size() ) return x; 
    if( to[x] != x ) return get_ans( to[x] , now + dep[to[x]] - dep[x] );
    int nxt = E[x][now % deg[x]];
    if( Lcm[x] == Lim + 1 || ( Lcm[nxt] <= Lim && Lcm[nxt] == Lcm[x] ) ){
        int res = get_ans( nxt , now + l[nxt] );
        to[x] = to[nxt];
        return res;
    }
    return get_ans( nxt , now + l[nxt] );
}

inline void clear(){
    for( int i = 1 ; i <= n ; i ++ ) E[i].clear(),f[i] = l[i] = deg[i] = dep[i] = Lcm[i] = to[i] = 0;
    n = q = 0;
}

inline void solve(){
    n = read(),q = read(); to[1] = 1;
    for( int i = 2 ; i <= n ; i ++ ) f[i] = read(),E[f[i]].emplace_back( i ),deg[f[i]] ++,to[i] = i;
    // cerr << deg[1] << "\n";
    for( int i = 2 ; i <= n ; i ++ ) l[i] = read();
    init( 1 , 1 );
    // for( int i = 1 ; i <= n ; i ++ ) cerr << (long long)Lcm[i] << "\n";
    for( int i = 1 ; i <= q ; i ++ ){
        int x = read();
        printf("%d ",(signed)get_ans( 1 , x ));
    }
    puts("");
    clear();
}

signed main(){
    int t = read();
    while( t -- ) solve();
    return 0;
}