logoChat01.ai

#include <bits/stdc++.h> #define int long long us...

Создано: 20 сентября 2026 г.

Отвечено с использованием GPT-5.6 от Chat01

Вопрос

#include <bits/stdc++.h>
#define int long long

using namespace std;

int N = 2e5;
int n, m;
vector<vector<int>> g;
vector <int> h, lg, pos, par, mx, num;
vector<vector<int>> pt;
vector<vector<int>> lc;
vector <int> p2;
int st = 20;

void upd(int v) {
for (int i = 1; i < st; i++) {
lc[i][v] = lc[i - 1][lc[i - 1][v]];
}
}

void dfs(int v, int p) {
lc[0][v] = p;
upd(v);
h[v] = h[p] + 1;
par[v] = p;
mx[v] = h[v];
for (auto to : g[v]) {
dfs(to, v);
mx[v] = max(mx[v], mx[to]);
}
}

void build(int v, int p) {
if (g[v].empty()) {
pt[v].push_back(v);
pos[v] = 0;
num[v] = v;
return;
}
int cv = v;
int cur = h[v];
for (auto to : g[v]) {
build(to, v);
if (mx[to] >= cur) {
cv = to;
cur = mx[to];
}
}
pt[num[cv]].push_back(v);
pos[v] = pt[num[cv]].size() - 1;
num[v] = num[cv];
}

int get(int v, int k) {
if (k == 0) {
return v;
}
v = lc[lg[k]][v];
k -= p2[lg[k]];
return pt[num[v]][pos[v] + k];
}

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
p2.resize(st);
p2[0] = 1;
for (int i = 1; i < st; i++) {
p2[i] = p2[i - 1] * 2;
}
cin >> n >> m;
int pw = 1;
lg.assign(N, 0);
int c = 0;
while (pw < N) {
lg[pw] = c;
pw = 2;
c++;
}
int cur = lg[1];
for (int i = 2; i < N; i++) {
if (lg[i]) {
cur = lg[i];
} else {
lg[i] = cur;
}
}
/
for (int i = 1; i < N; i++) {
cout << i << " " << lg[i] << "\n";
}*/
lc.assign(st, vector<int>(n, 0));
g.resize(n);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
g[p].push_back(i);
}
h.assign(n, 0);
par.assign(n, 0);
mx.resize(n);
dfs(0, 0);
pt.resize(n);
pos.resize(n);
num.resize(n);
build(0, 0);
for (int i = 0; i < n; i++) {
if (pt[i].empty()) {
continue;
}
int sz = pt[i].size();
int v = par[pt[i][sz - 1]];
while (sz) {
sz--;
pt[i].push_back(v);
v = par[v];
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
int v, k;
cin >> v >> k;
ans += get(v, k);
}
cout << ans;
}
решаю задачу о нахождении kth предка выдает ва4 найди тест на котором ломается если что в запросе k <= n - 1

Ответ

Проверю это не на глаз, а перебором маленьких деревьев: сравню твой get(v,k) с обычным подъёмом по par и найду минимальный контрпример.

Мысль

Brute-forced tree decomposition counterexamples and validated successor queries

Ответ

Есть важный момент: ограничение k <= n-1 само по себе не означает k <= depth(v). Я отдельно проверяю случаи, где запрос поднимается выше корня — твоя структура должна либо корректно возвращать корень, либо это может быть источником WA, в зависимости от условия задачи.

Мысль

Checking tree logic

I’m verifying whether the ancestor-jump construction covers every valid query. The table sizing and path extension appear consistent, but I’m still checking boundary cases where the remaining distance approaches a node’s depth.

Validated Kth ancestor implementation and found counterexamples

Ответ

Первый контрпример уже есть, но он использует k > depth(v). Сейчас отделяю это от настоящей ошибки алгоритма: если по условию k-й предок гарантированно существует, такой тест не считается.

Мысль

Verifying Tree Ancestor Queries Exhaustively

Worked for 2m 6s

Ответ

Нашёл тест, на котором код ломается, если по условию гарантируется только k <= n - 1, но не гарантируется k <= depth(v):

text
15 1
0 0 0 0 4 4 3 7 0 2 6 1 12 2
4 14

Дерево задаётся родителями:

text
par[1] = 0
par[2] = 0
par[3] = 0
par[4] = 0
par[5] = 4
par[6] = 4
par[7] = 3
par[8] = 7
par[9] = 0
par[10] = 2
par[11] = 6
par[12] = 1
par[13] = 12
par[14] = 2

Запрос:

text
v = 4, k = 14

У вершины 4 глубина всего 1, поэтому после первого шага мы уже в корне. Если считать, что предок корня — сам корень, правильный ответ 0.

У тебя происходит:

cpp
v = lc[lg[14]][4];

lg[14] = 3, то есть прыжок на 8 вверх. Из-за того что у корня:

cpp
lc[*][0] = 0

получаем v = 0.

Дальше:

cpp
k -= 8; // k = 6
return pt[num[0]][pos[0] + 6];

И вот здесь проблема: массив pt[num[0]] не обязан иметь столько элементов. Ты выходишь за границы vector, получаешь UB, и у меня на этом тесте программа выдала 81.

То есть проблема именно здесь:

cpp
return pt[num[v]][pos[v] + k];

при слишком большом k.

При этом я отдельно перебрал все деревья до n = 9 для запросов, где

cpp
k <= depth(v)

и ошибок не нашёл. То есть сама идея get() у тебя, похоже, корректна для случая, когда k-й предок действительно существует.

Если по условию запрос может иметь k > depth(v), можно в начале сделать:

cpp
int get(int v, int k) {
    k = min(k, h[v] - 1);

    if (k == 0) {
        return v;
    }

    v = lc[lg[k]][v];
    k -= p2[lg[k]];
    return pt[num[v]][pos[v] + k];
}

Почему h[v] - 1: у тебя из-за

cpp
h[v] = h[p] + 1;
dfs(0, 0);

получается

text
h[0] = 1

а обычная глубина корня равна 0.

Если же в задаче гарантировано k <= depth(v), тогда этот контрпример не подходит — и нужно искать другой источник WA, например формат ввода/индексацию. В таком случае скинь условие задачи или ссылку: по самому алгоритму для существующего k-го предка на малых деревьях ошибка пока не воспроизводится.

Поделиться этим Q&A