logoChat01.ai

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

Tạo vào: 20 tháng 9, 2026

Trả lời bằng GPT-5.6 bởi Chat01

Câu hỏi

#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

Trả lời

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

Suy nghĩ

Brute-forced tree decomposition counterexamples and validated successor queries

Trả lời

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

Suy nghĩ

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

Trả lời

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

Suy nghĩ

Verifying Tree Ancestor Queries Exhaustively

Worked for 2m 6s

Trả lời

Нашёл тест, на котором код ломается, если по условию гарантируется только 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-го предка на малых деревьях ошибка пока не воспроизводится.

Chia sẻ Q&A này