题解：CF2223C Zhily and Signpost

· · 题解

为啥你们写这么麻烦，感觉我就是写了个暴力然后过了。

考虑离线下来，每个点存一个东西 (r,M)，表示：当前节点内的所有询问 i 都满足 m_i\bmod M=r。

我们无非就是，自上而下地将某个节点的询问推到儿子处。我们发现：

  1. 若 M\mid d_u 或者 M>10^{18}，所有点都必然被分到同一个儿子处。
  2. 否则，我们将每个询问暴力下传，M 变为 \operatorname{lcm}(M,d_u)，r 直接重算。

我们来证明这个暴力的复杂度是 \mathcal{O}(q\log V) 的。显然，对于每个询问，若其被暴力分组了，对应的 M 至少翻倍，因此每个元素只会参与 \log V 次分组，均摊复杂度正确。

代码，超级好写啊。不知道大家在 CRT 啥东西。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 5e5 + 10;
const ll inf = 1 + (ll)1e18;

inline 
ll lcm(ll x, ll y) {
    if (x >= inf || y >= inf) return inf;
    ll d = gcd(x, y); __int128 res = (__int128)x / d * y;
    return res >= inf ? inf : res;
}

vector<int> g[MAXN];

int T, n, q, fa[MAXN], ans[MAXN << 1]; ll w[MAXN], m[MAXN << 1];

void dfs(int u, ll r, ll mod, vector<int> &query) {
    if (g[u].empty()) { for (int i : query) ans[i] = u; return ; }
    int d = g[u].size();
    if (mod >= inf || mod % d == 0) return dfs(g[u][(r + w[u]) % d], r, mod, query);
    vector<vector<int>> tmp(d);
    for (int i : query) tmp[(m[i] + w[u]) % d].emplace_back(i);
    vector<int>().swap(query); ll tmod = lcm(mod, d);
    for (int i = 0; i < d; i++) {
        if (!tmp[i].empty()) dfs(g[u][i], m[tmp[i][0]] % tmod, tmod, tmp[i]);
    }
}

int main() {
    for (scanf("%d", &T); T--; ) {
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), g[fa[i]].emplace_back(i);
        for (int i = 2, x; i <= n; i++) scanf("%d", &x), w[i] = w[fa[i]] + x;
        vector<int> query;
        for (int i = 1; i <= q; i++) scanf("%lld", &m[i]);
        for (int i = 1; i <= q; i++) query.emplace_back(i);
        dfs(1, 0, 1, query);
        for (int i = 1; i <= q; i++) printf("%d ", ans[i]); puts("");
    }
}