Дано дерево из n вершин. У каждой вершины есть цве...

Главная проблема в том, что у тебя серьёзно перепутана логика центроид-декомпозиции и запросов.

Разберу по пунктам, что именно не так, а потом дам исправленный рабочий код.

---

Что не так в твоём коде

1. par и vec заполняются только для центроидов, но query думает, что они есть для всех вершин

В build:

cpp
par[c] = {prev, d + 1};
f(c, 1, c, c);
used[c] = 1;

где c — очередной центроид. То есть:

• par[c] задаётся только для центроидов.
• vec[c] тоже заполняется только для центроидов в f.

Но в main:

cpp
cout << query(v, c, 0) << " ";

и в query:

cpp
int query(int v, int c, int d) {
    if (vec[v][c] >= 1) {        // <-- v может быть НЕ центроидом
        res = min(res, vec[v][c] + d);
    }
    while (par[v].first != -1) { // <-- par[v] для обычных вершин не задавался
        d += par[v].second;
        v = par[v].first;
        if (vec[v][c] >= 1) {
            res = min(res, vec[v][c] + d);
        }
    }
    ...
}

Проблемы:

• Для обычных вершин par[v] и vec[v] никогда не инициализировались, но ты их читаешь → неопределённое поведение.
• par[v].first по умолчанию будет (0, 0), т.е. par[v].first != -1, и цикл может ходить по мусорным данным.

В корректной центроид-декомпозиции:

• Для каждой вершины надо хранить список пар (центроид, расстояние до этого центроида).
• А для каждого центроида — агрегированную информацию (например, best[centroid][color]).

Запрос устроен так:

text
ans = min по всем (c, dist(v,c)) из списка для v:
          dist(v,c) + best[c][color]

А не поднятием по par[v], как у тебя.

---

2. Неправильное использование map через operator[] как проверки существования

В f:

cpp
if (vec[c][col[v]] >= 1) {
    vec[c][col[v]] = min(vec[c][col[v]], d);
} else {
    vec[c][col[v]] = d;
}

vec[c][col[v]]:

• Если ключа ещё нет, operator[] создаёт его со значением 0.
• То есть ты не проверяешь наличие, а создаёшь запись и работаешь с 0 как с «значения ещё не было».

Из-за этого тебе пришлось:

• начинать расстояния с d = 1,
• в query потом возвращать res - 1.

Это костыль. Нормально делается так:

cpp
auto &mp = vec[c];
int color = col[v];
auto it = mp.find(color);
if (it == mp.end()) mp[color] = d;
else it->second = min(it->second, d);

---

3. Странная логика с расстояниями (d с 1, res - 1 в конце)

В build:

cpp
f(c, 1, c, c);

и в query:

cpp
return res - 1;

Ты искусственно:

• добавляешь 1 ко всем расстояниям;
• потом в конце вычитаешь 1.

Это опять же следствие того, что ты используешь 0 как «нет значения» в map. Это можно исправить аккуратной работой с map::find / count.

---

4. par используется как «родитель центроида», но для вершины v в запросе ты считаешь, что par[v] задаёт подъём по дереву центроидов → логически неверно

par в build хранит:

cpp
par[c] = {prev, d + 1};

где prev — родитель центроидов в дереве центроидов. Но ты никогда не задаёшь par для обычных вершин, то есть вершину v ты не привязываешь к цепочке центроидов. Для корректной работы нужно отдельное хранилище для каждого v:

cpp
vector<vector<pair<int,int>>> up; // up[v] = { (centroid, dist) ... }

и использовать именно его в запросах.

---

Исправленный рабочий код

Ниже — переработанный вариант с нормальной центроид-декомпозицией:

• Для каждого центроида c:
  • best[c][color] — минимальное расстояние от c до вершины этого цвета.
• Для каждой вершины v:
  • up[v] — список (c, dist(v,c)) по всем центроидам на пути в дереве центроидов.

Запрос (v, color):

cpp
ans = min по (c, dist_v_c) из up[v], если в best[c] есть этот color:
          dist_v_c + best[c][color]

Код

cpp
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> g;
vector<int> col;
vector<int> sz;
vector<int> used;

// up[v] = список (центроид, расстояние от v до этого центроида)
vector<vector<pair<int,int>>> up;

// best[c][color] = минимальное расстояние от центроида c до вершины цвета color
vector<map<int,int>> best;

void dfs_size(int v, int p) {
    sz[v] = 1;
    for (int to : g[v]) {
        if (to == p || used[to]) continue;
        dfs_size(to, v);
        sz[v] += sz[to];
    }
}

int find_centroid(int v, int p, int total) {
    for (int to : g[v]) {
        if (to == p || used[to]) continue;
        if (sz[to] > total / 2) {
            return find_centroid(to, v, total);
        }
    }
    return v;
}

// Обходим компоненту от центроида c, считаем расстояния до него и обновляем best/ up
void dfs_add(int v, int p, int c, int dist) {
    // Запомним, что вершина v на расстоянии dist от центроида c
    up[v].push_back({c, dist});

    // Обновляем лучший ответ по цвету для центроида c
    auto &mp = best[c];
    int color = col[v];
    auto it = mp.find(color);
    if (it == mp.end() || dist < it->second)
        mp[color] = dist;

    for (int to : g[v]) {
        if (to == p || used[to]) continue;
        dfs_add(to, v, c, dist + 1);
    }
}

void build(int v) {
    dfs_size(v, -1);
    int c = find_centroid(v, -1, sz[v]); // нашли центроид
    used[c] = 1;

    // из центроида c обойдём его компоненту и заполним up / best
    dfs_add(c, -1, c, 0);

    // рекурсивно строим для оставшихся компонент
    for (int to : g[c]) {
        if (!used[to]) {
            build(to);
        }
    }
}

// запрос: расстояние от v до ближайшей вершины цвета color
int query(int v, int color) {
    const int INF = (int)1e9;
    int ans = INF;

    for (auto [c, dist_to_c] : up[v]) {
        auto &mp = best[c];
        auto it = mp.find(color);
        if (it != mp.end()) {
            ans = min(ans, dist_to_c + it->second);
        }
    }

    return (ans == INF ? -1 : ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    g.assign(n, {});
    col.resize(n);
    sz.assign(n, 0);
    used.assign(n, 0);
    up.assign(n, {});
    best.assign(n, {});

    // дерево по родителям
    for (int i = 0; i < n - 1; i++) {
        int p;
        cin >> p;          // p — отец вершины (i+1)
        g[p].push_back(i + 1);
        g[i + 1].push_back(p);
    }

    // цвета вершин
    for (int i = 0; i < n; i++) {
        cin >> col[i];
    }

    // строим центроид-декомпозицию
    build(0);

    int q;
    cin >> q;
    while (q--) {
        int v, c;
        cin >> v >> c;
        cout << query(v, c) << ' ';
    }
    return 0;
}

---

Если хочешь, могу отдельно нарисовать картинку, как именно формируются up[v] и best[c] на простом примере дерева, чтобы было наглядно, как работают запросы.