题解归档 - cf2224E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2224E
• 本地来源：problems/cf2224E/idea.md
• 题目链接：https://codeforces.com/contest/2224/problem/E
• 原始标题：cf2224E - Zhily and Signpost

思路

cf2224E - Zhily and Signpost

Pattern

For a fixed query value m, the arrival time at node u is always
m + dist[u], where dist[u] is the root-to-u edge length sum. Therefore
the choice at u is determined by:

(m + dist[u]) mod deg[u].

So each visited node adds one congruence constraint on the original query value
m.

Claim

Maintain a batch of queries known to satisfy one congruence class
m = r (mod M) at the current node.

• If deg[u] divides M, every query in the batch chooses the same child, so
  the whole batch can be moved without inspecting individual queries.
• Otherwise, split the batch by (m + dist[u]) mod deg[u]; for each child,
  merge the old congruence with the new one using CRT.

Whenever the modulus grows above 1e18, a congruence class contains at most one
distinct input query value because all queries satisfy 0 <= m <= 1e18; from
there direct single-value simulation is safe.

Algorithm

Compress duplicate query values, solve answers for unique values, then map back
to original query positions.

Run recursive batch routing from the root:

1. While the current modulus already decides the node's outgoing edge, jump the
   whole batch through that edge.
2. If a leaf is reached, assign that leaf to the whole batch.
3. Otherwise split unique query ids by the currently chosen child.
4. For each non-empty child bucket, CRT-merge the new residue condition and
   continue.

Complexity

Every per-query split happens only when the maintained modulus increases. Long
chains whose branch is already determined are processed as whole batches.
Memory is linear in n + q.

Checks

• python tools/run_exe.py cf2224E - sample OK.
• python tools/stress2.py cf2224E -n 1000 --keep-fail - OK against direct
  path simulation on random small trees and queries.

代码

来源：problems/cf2224E/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
using ull=unsigned long long;
using i128=__int128_t;
const ull LIM=1000000000000000000ULL;
int n,q;
vector<vector<int> > e;
vector<ull> dep,vl;
vector<int> an;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll x1,y1,g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return g;
}

ll invmod(ll a,ll mod){
    ll x,y;
    exgcd(a,mod,x,y);
    x%=mod;
    if(x<0) x+=mod;
    return x;
}

int walk(int u,ull m){
    while(!e[u].empty()){
        ull d=e[u].size();
        int k=(int)((m%d+dep[u]%d)%d);
        u=e[u][k];
    }
    return u;
}

void solve(int u,i128 r,ull mod,vector<int> v){
    while(!e[u].empty()){
        ull d=e[u].size();
        if(mod%d) break;
        int k=(int)(((ull)(r%d)+dep[u]%d)%d);
        u=e[u][k];
    }
    if(e[u].empty()){
        for(int x:v) an[x]=u;
        return;
    }
    int d=(int)e[u].size();
    vector<vector<int> > buk(d);
    vector<int> used;
    for(int x:v){
        int k=(int)((vl[x]%d+dep[u]%d)%d);
        if(buk[k].empty()) used.push_back(k);
        buk[k].push_back(x);
    }
    for(int k:used){
        ull g=std::gcd(mod,(ull)d);
        ull d1=d/g;
        ull a=(k+(ull)d-dep[u]%d)%d;
        ull rd=(ull)(r%d);
        ull diff=(a+(ull)d-rd)%d;
        ull rhs=diff/g;
        ull t=0;
        if(d1>1){
            ull m1=(mod/g)%d1;
            t=(ull)((i128)rhs*invmod((ll)m1,(ll)d1)%d1);
        }
        i128 nmod=(i128)(mod/g)*d;
        i128 nr=(r+(i128)mod*t)%nmod;
        if(nmod>(i128)LIM){
            for(int x:buk[k]) an[x]=walk(e[u][k],vl[x]);
        }else{
            solve(e[u][k],nr,(ull)nmod,move(buk[k]));
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        cin>>n>>q;
        vector<int> fa(n+1);
        e.assign(n+1,{});
        for(int i=2;i<=n;i++){
            cin>>fa[i];
            e[fa[i]].push_back(i);
        }
        vector<ull> len(n+1);
        for(int i=2;i<=n;i++) cin>>len[i];
        dep.assign(n+1,0);
        for(int i=2;i<=n;i++) dep[i]=dep[fa[i]]+len[i];
        vector<pair<ull,int> > ord(q);
        for(int i=0;i<q;i++){
            ull x;
            cin>>x;
            ord[i]={x,i};
        }
        sort(ord.begin(),ord.end());
        vl.clear();
        vector<int> id(q);
        for(int i=0;i<q;i++){
            if(i==0||ord[i].first!=ord[i-1].first) vl.push_back(ord[i].first);
            id[ord[i].second]=(int)vl.size()-1;
        }
        an.assign(vl.size(),1);
        vector<int> all(vl.size());
        iota(all.begin(),all.end(),0);
        solve(1,0,1,move(all));
        for(int i=0;i<q;i++){
            if(i) cout<<" ";
            cout<<an[id[i]];
        }
        cout<<"\n";
    }
    return 0;
}