Problema knight — OJI 2026, Clasa XI-XII, rezolvare explicată

Algoritmul, pas cu pas

O mutare urcă 2 niveluri (la bunic $y$ ) și coboară la un frate al părintelui ( $v$ , fiu al lui $y$ , $\ne x$ ). Deci după fiecare mutare, părintele poziției curente urcă un nivel pe lanțul de strămoși ai lui $a$ .

Accesibilitate. $b$ e accesibil din $a$ $\iff$ părintele lui $b$ e un strămoș al lui $a$ la nivelul potrivit ( $j = \text{adânc}(a) - \text{adânc}(b) + 1 \ge 2$ ) și $b$ nu e strămoșul lui $a$ de pe nivelul $\text{adânc}(b)$ .

Număr de trasee. La fiecare pas intermediar alegem un frate (fiu al bunicului $\ne$ părinte): $\text{nr. fii} - 1$ opțiuni. Ultimul pas e fixat la $b$ . Deci:

$\text{nr. trasee} = \prod_{t=2}^{j-1} (\deg(p_t) - 1)$

unde $p_t$ sunt strămoșii lui $a$ și $\deg$ = numărul de fii. Calculez strămoșul la o adâncime dată și produsul pe intervalul de strămoși cu binary lifting, în $O(\log N)$ pe interogare. C2 = produs nenul (niciun strămoș din interval cu un singur fiu); C3 = produsul, modulo $10^9+7$ .

Soluția în C++

#include <fstream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;
ifstream fin("knight.in");
ofstream fout("knight.out");

int main() {
    int C, N;
    fin >> C >> N;
    vector<int> par(N + 1, 0), deg(N + 1, 0), depth(N + 1, 0);
    for (int i = 2; i <= N; i++) { fin >> par[i]; deg[par[i]]++; }
    for (int i = 2; i <= N; i++) depth[i] = depth[par[i]] + 1; // par[i] < i

    if (C == 1) {
        int cnt = 0;
        for (int u = 1; u <= N; u++) if (deg[u] == 1) cnt++;
        fout << cnt << "\n";
        return 0;
    }

    int LOG = 1; while ((1 << LOG) <= N) LOG++;
    vector<vector<int>> up(LOG, vector<int>(N + 1, 0)), zero(LOG, vector<int>(N + 1, 0));
    vector<vector<long long>> prod(LOG, vector<long long>(N + 1, 1));
    for (int u = 1; u <= N; u++) {
        up[0][u] = par[u];
        if (par[u]) { prod[0][u] = ((deg[par[u]] - 1) % MOD + MOD) % MOD; zero[0][u] = (deg[par[u]] == 1); }
    }
    for (int k = 1; k < LOG; k++) for (int u = 1; u <= N; u++) {
        int mid = up[k - 1][u];
        up[k][u] = up[k - 1][mid];
        prod[k][u] = (prod[k - 1][u] * prod[k - 1][mid]) % MOD;
        zero[k][u] = zero[k - 1][u] + zero[k - 1][mid];
    }
    auto kthAnc = [&](int u, int s) { for (int k = 0; k < LOG && u; k++) if (s & (1 << k)) u = up[k][u]; return u; };
    auto rangeUp = [&](int u, int s, long long &pr, int &zr) { pr = 1; zr = 0;
        for (int k = 0; k < LOG && u; k++) if (s & (1 << k)) { pr = (pr * prod[k][u]) % MOD; zr += zero[k][u]; u = up[k][u]; } };

    int Q; fin >> Q;
    while (Q--) {
        int a, b; fin >> a >> b;
        long long ans = 0; bool reach = false;
        if (b != 1) {
            int da = depth[a], db = depth[b];
            int j = da - (db - 1);
            if (j >= 2 && kthAnc(a, da - (db - 1)) == par[b] && kthAnc(a, da - db) != b) {
                reach = true;
                long long pr = 1; int zr = 0;
                if (j - 2 > 0) rangeUp(par[a], j - 2, pr, zr); // produs (deg-1) peste p_2..p_{j-1}
                ans = pr;
                if (C == 2) ans = (zr == 0) ? 1 : 0;
            }
        }
        fout << (reach ? ans : 0) << "\n";
    }
    return 0;
}

Greșeli frecvente

Crezi că mutarea schimbă subarborele — de fapt urci 2 niveluri și cobori la un frate al părintelui; poziția „urcă" un nivel per mutare.
Tratezi accesibilitatea fără verificarea strămoșului — părintele lui $b$ trebuie să fie chiar strămoșul lui $a$ la adâncimea $\text{adânc}(b)-1$ .
Răspunzi pe fiecare interogare cu BFS — $O(N \cdot Q)$ e prea lent; folosește binary lifting pentru produs și strămoși.

Algoritmul, pas cu pas

O mutare urcă 2 niveluri (la bunic

y

) și coboară la un frate al părintelui (

v

, fiu al lui

y

\ne x

). Deci după fiecare mutare, părintele poziției curente urcă un nivel pe lanțul de strămoși ai lui

a

Accesibilitate.

b

e accesibil din

a

\iff

părintele lui

b

e un strămoș al lui

a

la nivelul potrivit (

j = \text{adânc}(a) - \text{adânc}(b) + 1 \ge 2

) și

b

nu e strămoșul lui

a

de pe nivelul

\text{adânc}(b)

Număr de trasee. La fiecare pas intermediar alegem un frate (fiu al bunicului

\ne

părinte):

\text{nr. fii} - 1

opțiuni. Ultimul pas e fixat la

b

. Deci:

\text{nr. trasee} = \prod_{t=2}^{j-1} (\deg(p_t) - 1)

unde

p_t

sunt strămoșii lui

a

și

\deg

= numărul de fii. Calculez strămoșul la o adâncime dată și produsul pe intervalul de strămoși cu binary lifting, în

O(\log N)

pe interogare. C2 = produs nenul (niciun strămoș din interval cu un singur fiu); C3 = produsul, modulo

10^9+7

Soluția în C++

#include <fstream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;
ifstream fin("knight.in");
ofstream fout("knight.out");

int main() {
    int C, N;
    fin >> C >> N;
    vector<int> par(N + 1, 0), deg(N + 1, 0), depth(N + 1, 0);
    for (int i = 2; i <= N; i++) { fin >> par[i]; deg[par[i]]++; }
    for (int i = 2; i <= N; i++) depth[i] = depth[par[i]] + 1; // par[i] < i

    if (C == 1) {
        int cnt = 0;
        for (int u = 1; u <= N; u++) if (deg[u] == 1) cnt++;
        fout << cnt << "\n";
        return 0;
    }

    int LOG = 1; while ((1 << LOG) <= N) LOG++;
    vector<vector<int>> up(LOG, vector<int>(N + 1, 0)), zero(LOG, vector<int>(N + 1, 0));
    vector<vector<long long>> prod(LOG, vector<long long>(N + 1, 1));
    for (int u = 1; u <= N; u++) {
        up[0][u] = par[u];
        if (par[u]) { prod[0][u] = ((deg[par[u]] - 1) % MOD + MOD) % MOD; zero[0][u] = (deg[par[u]] == 1); }
    }
    for (int k = 1; k < LOG; k++) for (int u = 1; u <= N; u++) {
        int mid = up[k - 1][u];
        up[k][u] = up[k - 1][mid];
        prod[k][u] = (prod[k - 1][u] * prod[k - 1][mid]) % MOD;
        zero[k][u] = zero[k - 1][u] + zero[k - 1][mid];
    }
    auto kthAnc = [&](int u, int s) { for (int k = 0; k < LOG && u; k++) if (s & (1 << k)) u = up[k][u]; return u; };
    auto rangeUp = [&](int u, int s, long long &pr, int &zr) { pr = 1; zr = 0;
        for (int k = 0; k < LOG && u; k++) if (s & (1 << k)) { pr = (pr * prod[k][u]) % MOD; zr += zero[k][u]; u = up[k][u]; } };

    int Q; fin >> Q;
    while (Q--) {
        int a, b; fin >> a >> b;
        long long ans = 0; bool reach = false;
        if (b != 1) {
            int da = depth[a], db = depth[b];
            int j = da - (db - 1);
            if (j >= 2 && kthAnc(a, da - (db - 1)) == par[b] && kthAnc(a, da - db) != b) {
                reach = true;
                long long pr = 1; int zr = 0;
                if (j - 2 > 0) rangeUp(par[a], j - 2, pr, zr); // produs (deg-1) peste p_2..p_{j-1}
                ans = pr;
                if (C == 2) ans = (zr == 0) ? 1 : 0;
            }
        }
        fout << (reach ? ans : 0) << "\n";
    }
    return 0;
}

Greșeli frecvente

Crezi că mutarea schimbă subarborele — de fapt urci 2 niveluri și cobori la un frate al părintelui; poziția „urcă" un nivel per mutare.
Tratezi accesibilitatea fără verificarea strămoșului — părintele lui $b$ trebuie să fie chiar strămoșul lui $a$ la adâncimea $\text{adânc}(b)-1$ .
Răspunzi pe fiecare interogare cu BFS — $O(N \cdot Q)$ e prea lent; folosește binary lifting pentru produs și strămoși.

knight

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

knight

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++