Advertisement
skimono

Untitled

May 26th, 2023
839
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.80 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <stack>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <string>
  12. #include <set>
  13. #include <deque>
  14. #include <queue>
  15. #include <map>
  16. #include <bitset>
  17. #include <random>
  18. #include <list>
  19. #include <unordered_map>
  20. #include <unordered_set>
  21. #include <cassert>
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef unsigned long long ull;
  27. typedef long double ld;
  28. typedef string str;
  29. //typedef __int128 ultraint;
  30. #define endl "\n"
  31. #define sqrt sqrtl
  32. #define F first
  33. #define S second
  34. #define all(vc666) vc666.begin(), vc666.end()
  35. #define pow binpow
  36. //#define Vec Point
  37.  
  38. const ll inf = (ll)1e18 + 7;
  39. ld EPS = 1e-9;
  40. ld Pi = 3.1415926535897932384;
  41.  
  42. ll binpow(ll a, ll n) {
  43.     ll res = 1;
  44.     while (n) {
  45.         if (n & 1) {
  46.             res *= a;
  47.         }
  48.         a *= a;
  49.         n >>= 1;
  50.     }
  51.     return res;
  52. }
  53. struct Node {
  54.     unordered_map<ll, ll> colors;
  55. };
  56. struct Node_help {
  57.     vector<ll> colors;
  58. };
  59. const ll sz1 = 1e5;
  60. const ll sz2 = 17;
  61. vector <Node_help> centroid_build_vertex;
  62. vector <Node> centroid_vertex;
  63. vector <ll> g[sz1];
  64. ll cl[sz1];
  65. ll d[sz1];
  66. pair <ll, ll> ti[sz1];
  67. ll up[sz1][sz2 + 1];
  68.  
  69. void dfs2(ll v, ll p, ll& time) {
  70.     ti[v].first = time++;
  71.     if (p == -1) {
  72.         d[v] = 0;
  73.         up[v][0] = 0;
  74.     }
  75.     else {
  76.         d[v] = d[p] + 1;
  77.         up[v][0] = p;
  78.     }
  79.     for (ll i = 1; i <= sz2; i++) {
  80.         up[v][i] = up[up[v][i - 1]][i - 1];
  81.     }
  82.     for (auto& u : g[v]) {
  83.         if (u != p) {
  84.             dfs2(u, v, time);
  85.         }
  86.     }
  87.     ti[v].second = time++;
  88. }
  89.  
  90. bool pred(ll a, ll b) {
  91.     return ti[a].first <= ti[b].first && ti[a].second >= ti[b].second;
  92. }
  93.  
  94. ll lca(ll a, ll b) {
  95.     if (pred(a, b)) {
  96.         return a;
  97.     }
  98.     for (ll i = sz2; i >= 0; i--) {
  99.         if (!pred(up[a][i], b)) {
  100.             a = up[a][i];
  101.         }
  102.     }
  103.     return up[a][0];
  104. }
  105.  
  106. ll get_dist(ll a, ll b) {
  107.     ll sup = lca(a, b);
  108.     return d[a] + d[b] - 2 * d[sup];
  109. }
  110.  
  111. struct Centroid_decomposition {
  112.     vector<vector<ll>> gr;
  113.     vector<ll> tree, siz;
  114.     ll root = -1;
  115.     Centroid_decomposition(ll n) {
  116.         tree.resize(n, -2);
  117.         siz.resize(n);
  118.     }
  119.     void sizes(ll v, ll p) {
  120.         siz[v] = 1;
  121.         for (ll& u : g[v]) {
  122.             if (u != p && tree[u] == -2) {
  123.                 sizes(u, v);
  124.                 siz[v] += siz[u];
  125.             }
  126.         }
  127.     }
  128.     ll centroid(ll v, ll p, ll s) {
  129.         for (ll& u : g[v]) {
  130.             if (u != p && tree[u] == -2 && siz[u] > s / 2) {
  131.                 return centroid(u, v, s);
  132.             }
  133.         }
  134.         return v;
  135.     }
  136.     void build(ll v, ll p) {
  137.         sizes(v, -1);
  138.         tree[v] = p;
  139.         if (p != -1) {
  140.             gr[v].push_back(p);
  141.             gr[p].push_back(v);
  142.         }
  143.         centroid_build_vertex[v].colors.push_back({ v });
  144.         for (ll& u : g[v]) {
  145.             if (tree[u] == -2) {
  146.                 build(centroid(u, -1, siz[u]), v);
  147.             }
  148.         }
  149.         for (ll& u : gr[v]) {
  150.             if (u != p) {
  151.                 if ((ll)centroid_build_vertex[v].colors.size() < centroid_build_vertex[u].colors.size()) {
  152.                     centroid_build_vertex[v].colors.swap(centroid_build_vertex[u].colors);
  153.                 }
  154.                 for (ll& i : centroid_build_vertex[u].colors) {
  155.                     centroid_build_vertex[v].colors.push_back(i);
  156.                 }
  157.                 centroid_build_vertex[u].colors.clear();
  158.             }
  159.         }
  160.         gr[v].clear();
  161.         for (ll& i : centroid_build_vertex[v].colors) {
  162.             ll x = get_dist(i, v);
  163.             if (centroid_vertex[v].colors.find(cl[i]) == centroid_vertex[v].colors.end()) {
  164.                 centroid_vertex[v].colors[cl[i]] = x;
  165.                 continue;
  166.             }
  167.             centroid_vertex[v].colors[cl[i]] = min(centroid_vertex[v].colors[cl[i]], x);
  168.         }
  169.     }
  170.     void build_tree() {
  171.         ll v = 0;
  172.         sizes(v, -1);
  173.         gr.resize(tree.size());
  174.         centroid_build_vertex.resize(tree.size());
  175.         centroid_vertex.resize(tree.size());
  176.         build(centroid(v, -1, siz[v]), -1);
  177.         gr.clear();
  178.         siz.clear();
  179.     }
  180. };
  181.  
  182. ll get(ll v, ll color, Centroid_decomposition& U) {
  183.     ll ans = inf;
  184.     ll v2 = v;
  185.     while (v2 != -1) {
  186.         auto& clrs = centroid_vertex[v2].colors;
  187.         auto it_c = clrs.find(color);
  188.         if (it_c != clrs.end()) {
  189.             ans = min(ans, (it_c->second) + get_dist(v, v2));
  190.         }
  191.         v2 = U.tree[v2];
  192.     }
  193.     if (ans == inf) {
  194.         ans = -1;
  195.     }
  196.     return ans;
  197. }
  198.  
  199. signed main() {
  200. #ifdef _DEBUG
  201.     freopen("input.txt", "r", stdin);
  202.     freopen("output.txt", "w", stdout);
  203. #endif
  204.     ios_base::sync_with_stdio(0);
  205.     cin.tie(NULL);
  206.     cout.tie(NULL);
  207.     ll t = 1;
  208.     //cin >> t;
  209.     while (t--) {
  210.         ll n, i, j, x, y, q, timer = 1, root;
  211.         cin >> n;
  212.         for (i = 1; i < n; i++) {
  213.             cin >> j;
  214.             g[j].push_back(i);
  215.             g[i].push_back(j);
  216.         }
  217.         for (i = 0; i < n; i++) {
  218.             cin >> cl[i];
  219.         }
  220.         dfs2(0, -1, timer);
  221.         centroid_vertex.resize(n);
  222.         centroid_build_vertex.resize(n);
  223.         Centroid_decomposition U(n);
  224.         U.build_tree();
  225.         cin >> q;
  226.         while (q--) {
  227.             cin >> i >> j;
  228.             cout << get(i, j, U) << ' ';
  229.         }
  230.         cout << endl;
  231.     }
  232.     //Deisgned by skimono
  233. }
  234.     //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement