Advertisement
ivnikkk

Untitled

May 18th, 2022
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.61 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef int ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. // вроде не особо должны эти массивы с этими структурами много занимать т к глубина дерева центроидов <=log2(n)
  10. struct Node {
  11.     // в массиве эта структура будет лежать в i позиции -> значит эта структура будет хранить значение для поддерева i
  12.     // ключ - цвет
  13.     // значение мультисет расстояний от детей в центроидном дереве до вершин с цветом ключа
  14.     unordered_map<ll, multiset<ll>> colors;
  15. };
  16. struct Node_help {
  17.  
  18.     // в массиве эта структура будет лежать в i позиции -> значит эта структура будет хранить значение для поддерева i
  19.     // просто все вершины поддерева i pair<> {значение цвета, номер вершины(лежащая в поддереве i) }
  20.     vector<pll> colors;
  21. };
  22. vector<Node_help> centroid_build_vertex;
  23. vector<Node> centroid_vertex;
  24. vector<ll> clr;
  25. vector<vector<ll>> g;
  26. const ll LG = 17;
  27. vector<vector<ll>> up;
  28. vector<ll> d;
  29.  
  30. void dfs(ll v, ll p) {
  31.     if (p == -1) {
  32.         d[v] = 0;
  33.         up[0][v] = 0;
  34.     }
  35.     else {
  36.         d[v] = d[p] + 1;
  37.     }
  38.     for (ll l = 1; l < LG; l++) {
  39.         up[l][v] = up[l - 1][up[l - 1][v]];
  40.     }
  41.     for (ll& u : g[v]) {
  42.         if (u != p) {
  43.             up[0][u] = v;
  44.             dfs(u, v);
  45.         }
  46.     }
  47. }
  48. ll get_lca(ll a, ll b) {
  49.     if (a == b)return a;
  50.     if (d[b] > d[a])swap(a, b);
  51.     for (ll i = LG - 1; i >= 0; i--) {
  52.         if (d[up[i][a]] >= d[b]) a = up[i][a];
  53.     }
  54.     if (a == b) return a;
  55.     for (ll i = LG - 1; i >= 0; i--) {
  56.         if (up[i][a] != up[i][b]) a = up[i][a], b = up[i][b];
  57.     }
  58.     return up[0][a];
  59. }
  60. ll get_dist(ll a, ll b) {
  61.     ll lca = get_lca(a, b);
  62.     return d[b] + d[a] - 2 * d[lca];
  63. }
  64. struct Centroid_decomposition {
  65.     vector<vector<ll>> gr;
  66.     vector<ll> tree, siz;
  67.     vector<bool> used;
  68.     ll root = -1;
  69.     Centroid_decomposition(ll n) {
  70.         tree.resize(n);
  71.         siz.resize(n);
  72.         used.resize(n);
  73.     }
  74.     void sizes(ll v, ll p) {
  75.         siz[v] = 1;
  76.         for (ll& u : g[v]) {
  77.             if (u != p && !used[u]) {
  78.                 sizes(u, v);
  79.                 siz[v] += siz[u];
  80.             }
  81.         }
  82.     }
  83.     ll centroid(ll v, ll p, ll s) {
  84.         for (ll& u : g[v]) {
  85.             if (u != p && !used[u] && siz[u] > s / 2) {
  86.                 return centroid(u, v, s);
  87.             }
  88.         }
  89.         return v;
  90.     }
  91.     void build(ll v, ll p) {
  92.         sizes(v, -1);
  93.         used[v] = 1;
  94.         tree[v] = p;
  95.         if (p != -1) {
  96.             gr[v].push_back(p);
  97.             gr[p].push_back(v);
  98.         }
  99.         centroid_build_vertex[v].colors.push_back({ clr[v],v });
  100.         for (ll& u : g[v]) {
  101.             if (!used[u]) {
  102.                 build(centroid(u, -1, siz[u]), v);
  103.             }
  104.         }
  105.         for (ll& u : gr[v]) {
  106.             if (u != p) {
  107.                 if ((ll)centroid_build_vertex[v].colors.size() < centroid_build_vertex[u].colors.size()) {
  108.                     centroid_build_vertex[v].colors.swap(centroid_build_vertex[u].colors);
  109.                 }
  110.                 for (pll& i : centroid_build_vertex[u].colors) {
  111.                     centroid_build_vertex[v].colors.push_back(i);
  112.                 }
  113.                 centroid_build_vertex[u].colors.clear();
  114.             }
  115.         }
  116.         for (pll& i : centroid_build_vertex[v].colors) {
  117.             centroid_vertex[v].colors[i.first].insert(get_dist(i.second, v));
  118.         }
  119.     }
  120.     void build_tree() {
  121.         ll v = 0;
  122.         sizes(v, -1);
  123.         gr.resize(tree.size());
  124.         centroid_build_vertex.resize(tree.size());
  125.         centroid_vertex.resize(tree.size());
  126.         build(centroid(v, -1, siz[v]), -1);
  127.         used.clear();
  128.         siz.clear();
  129.     }
  130. };
  131. signed main() {
  132. #ifdef _DEBUG
  133.     freopen("input.txt", "r", stdin);
  134.     freopen("output.txt", "w", stdout);
  135. #endif
  136.     ios_base::sync_with_stdio(false);
  137.     cin.tie(nullptr);
  138.     cout.tie(nullptr);
  139.     ll n;
  140.     cin >> n;
  141.     g.resize(n);
  142.     clr.resize(n);
  143.     for (ll i = 0; i < n - 1; i++) {
  144.         ll x;
  145.         cin >> x;
  146.         g[x].push_back(i + 1);
  147.         g[i + 1].push_back(x);
  148.     }
  149.     for (ll i = 0; i < n; i++) {
  150.         cin >> clr[i];
  151.     }
  152.     up.resize(LG, vector<ll>(n));
  153.     d.resize(n);
  154.     dfs(0, -1);
  155.     centroid_vertex.resize(n);
  156.     centroid_build_vertex.resize(n);
  157.     Centroid_decomposition U(n);
  158.     U.build_tree();
  159.     ll q;
  160.     cin >> q;
  161.     while (q--) {
  162.         ll v, c;
  163.         cin >> v >> c;
  164.         ll it = v;
  165.         ll ans = INT_MAX;
  166.         while (it != -1) {
  167.             if (!centroid_vertex[it].colors[c].empty()) {
  168.                 auto x = *centroid_vertex[it].colors[c].begin();
  169.                 ans = min(ans, x + get_dist(v, it));
  170.             }
  171.             it = U.tree[it];
  172.         }
  173.         if (ans == INT_MAX) {
  174.             cout << -1 << ' ';
  175.         }
  176.         else {
  177.             cout << ans << ' ';
  178.         }
  179.     }
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement