Advertisement
titovtima

Untitled

Oct 25th, 2020
881
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <cmath>
  6. #include <map>
  7. #include <queue>
  8. #include <list>
  9. #include <set>
  10.  
  11. #pragma gcc optimize("Ofast,no-stack-protector,tune=native")
  12. #pragma gcc optimize("sse,sse2,sse3,sse4,ssse3")
  13. #pragma gcc optimize("abm,mmx,avx,avx2,unroll-loops,fast-math,section-anchors")
  14.  
  15. //freopen(".in", "r", stdin);
  16. //freopen(".out", "w", stdout);
  17.  
  18. using namespace std;
  19. using ld = long double;
  20. using ll = long long;
  21. using ull = unsigned long long;
  22. //#define int ll
  23.  
  24. int n;
  25.  
  26. vector<vector<int>> rebr;
  27. //vector<int> par;
  28. vector<int> used;
  29. vector<int> subtreesize;
  30. vector<int> col;
  31.  
  32. vector<vector<int>> rebrcd;
  33. vector<int> parcd;
  34. vector<int> deepcd;
  35. vector<map<int,int>> ways;
  36. vector<map<int,int>> wayscol;
  37.  
  38. int dfscount(int v) {
  39.     int res = 1;
  40.     used[v] = 1;
  41.     for (auto u : rebr[v])
  42.         if (used[u] == 0)
  43.             res += dfscount(u);
  44.     subtreesize[v] = res;
  45.     return res;
  46. }
  47.  
  48. pair<int,int> cd(int v, int root, int deep = 0) {
  49. //    cout << "MUuuu ";
  50.     used[v] = 1;
  51. //    cout << "Hi from " << v << "\n";
  52.     for (auto u: rebr[v]) {
  53.         if (used[u] == 0 && ((ll)subtreesize[u] * 2 > subtreesize[root])) {
  54. //            cout << "Go to " << u << "\n";
  55.             pair<int,int> p = cd(u, root, deep);
  56.             subtreesize[v] -= p.second;
  57.             used[v] = 0;
  58.             if (v == root) {
  59.                 auto [nc, ns] = cd(v, v, deep + 1);
  60. //                rebrcd[nc].push_back(c);
  61.                 rebrcd[p.first].push_back(nc);
  62.                 parcd[nc] = p.first;
  63.             }
  64.             return p;
  65.         }
  66.     }
  67.     used[v] = 2;
  68.     deepcd[v] = deep;
  69. //    cout << "KUKU\n";
  70.     for (auto u: rebr[v])
  71.         if (used[u] == 0) {
  72.             auto [c, s] = cd(u, u, deep + 1);
  73. //            rebrcd[c].push_back(v);
  74.             rebrcd[v].push_back(c);
  75.             parcd[c] = v;
  76.         }
  77.     return {v, subtreesize[v]};
  78. }
  79.  
  80. void dfsways(int v, int to, int way = 0) {
  81.     used[v] = deepcd[to];
  82.     if (wayscol[to][col[v]] == 0 || wayscol[to][col[v]] > way + 1)
  83.         wayscol[to][col[v]] = way + 1;
  84.     if (v == to)
  85.         used[v] = n;
  86. //    ways[v][to] = way;
  87.     ways[to][v] = way;
  88.     for (auto i: rebr[v])
  89.         if (used[i] < deepcd[to])
  90.             dfsways(i, to, way+1);
  91. }
  92.  
  93. void findways(int v) {
  94.     dfsways(v, v);
  95.     for (int i: rebrcd[v])
  96.         if (deepcd[i] > deepcd[v])
  97.             findways(i);
  98. }
  99.  
  100. signed main() {
  101.     ios::sync_with_stdio(0);
  102.     cin.tie(0);
  103.     cout.tie(0);
  104.  
  105.     freopen("centroid.in", "r", stdin);
  106.     freopen("centroid.out", "w", stdout);
  107.  
  108.     cin >> n;
  109. //    cout << n << "\n";
  110.  
  111.     rebr = *(new vector<vector<int>>(n));
  112. //    par = vector<int>(n);
  113.  
  114. //    par[0] = 0;
  115.  
  116.     for (int i = 1; i < n; i++) {
  117.         int p;
  118.         cin >> p;
  119. //        p--;
  120. //        par[i] = p;
  121.         rebr[i].push_back(p);
  122.         rebr[p].push_back(i);
  123.     }
  124.  
  125.     col = *(new vector<int>(n));
  126.  
  127.     for (int i = 0; i < n; i++) {
  128.         cin >> col[i];
  129.     }
  130.  
  131.     used = *(new vector<int>(n, 0));
  132.     subtreesize = *(new vector<int>(n));
  133.     dfscount(0);
  134.  
  135.     rebrcd = *(new vector<vector<int>>(n));
  136.     parcd = *(new vector<int>(n));
  137.     deepcd = *(new vector<int>(n));
  138.  
  139. //    cout << "qq\n";
  140.  
  141.     used = *(new vector<int>(n, 0));
  142.     cd(0,0);
  143.  
  144.     int rootcd;
  145.     for (int i = 0; i < n; i++)
  146.         if (deepcd[i] == 0)
  147.             rootcd = i;
  148.  
  149.     used = *(new vector<int>(n, -1));
  150.     ways = *(new vector<map<int,int>>(n));
  151.     wayscol = *(new vector<map<int,int>>(n));
  152.  
  153. //    cout << "Hi\n";
  154.  
  155.     findways(rootcd);
  156.  
  157. //    for (int i = 0; i < n; i++) {
  158. //        for (auto [c, s] : ways[i])
  159. //            cout << "[" << c << "," << s << "] ";
  160. //        cout << "\n";
  161. //    }
  162. //
  163. //    for (int i = 0; i < n; i++) {
  164. //        for (auto [c, s] : wayscol[i])
  165. //            cout << "[" << c << "," << s << "] ";
  166. //        cout << "\n";
  167. //    }
  168.  
  169.     int m;
  170.     cin >> m;
  171.  
  172.     for (int qq = 0; qq < m; qq++) {
  173.         int v, c;
  174.         cin >> v >> c;
  175. //        v--;
  176.  
  177.         int res = wayscol[v][c];
  178.         int u = v;
  179.         while (u != rootcd) {
  180.             u = parcd[u];
  181.             if (wayscol[u][c] != 0 && (ways[u][v] + wayscol[u][c] < res || res == 0)) {
  182.                 res = ways[u][v] + wayscol[u][c];
  183.             }
  184.         }
  185.  
  186.         cout << res - 1 << " ";
  187. //        if (res > 0)
  188. //            cout << res - 1 << " ";
  189. //        else
  190. //            cout << "-1 ";
  191.     }
  192.  
  193.     return 0;
  194. }
  195.  
  196. /*
  197. 5
  198. 0 1 1 3
  199. 1 2 3 2 1
  200. 9
  201. 0 1
  202. 0 2
  203. 0 3
  204. 1 0
  205. 2 1
  206. 2 2
  207. 3 3
  208. 3 1
  209. 4 2
  210.  
  211.  
  212.  
  213. 8
  214. 1 1
  215. 2 2
  216. 3 3
  217. 4 4
  218. 5 5
  219. 6 6
  220. 7 7
  221. 3
  222. 3 6
  223. 3 2
  224. 1 2
  225.  
  226. 3
  227. 2
  228. 1
  229.  
  230.  */
  231.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement