Advertisement
ivnikkk

Untitled

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