Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <map>
- #include <queue>
- #include <list>
- #include <set>
- #pragma gcc optimize("Ofast,no-stack-protector,tune=native")
- #pragma gcc optimize("sse,sse2,sse3,sse4,ssse3")
- #pragma gcc optimize("abm,mmx,avx,avx2,unroll-loops,fast-math,section-anchors")
- //freopen(".in", "r", stdin);
- //freopen(".out", "w", stdout);
- using namespace std;
- using ld = long double;
- using ll = long long;
- using ull = unsigned long long;
- //#define int ll
- int n;
- vector<vector<int>> rebr;
- //vector<int> par;
- vector<int> used;
- vector<int> subtreesize;
- vector<int> col;
- vector<vector<int>> rebrcd;
- vector<int> parcd;
- vector<int> deepcd;
- vector<map<int,int>> ways;
- vector<map<int,int>> wayscol;
- int dfscount(int v) {
- int res = 1;
- used[v] = 1;
- for (auto u : rebr[v])
- if (used[u] == 0)
- res += dfscount(u);
- subtreesize[v] = res;
- return res;
- }
- pair<int,int> cd(int v, int root, int deep = 0) {
- // cout << "MUuuu ";
- used[v] = 1;
- // cout << "Hi from " << v << "\n";
- for (auto u: rebr[v]) {
- if (used[u] == 0 && ((ll)subtreesize[u] * 2 > subtreesize[root])) {
- // cout << "Go to " << u << "\n";
- pair<int,int> p = cd(u, root, deep);
- subtreesize[v] -= p.second;
- used[v] = 0;
- if (v == root) {
- auto [nc, ns] = cd(v, v, deep + 1);
- // rebrcd[nc].push_back(c);
- rebrcd[p.first].push_back(nc);
- parcd[nc] = p.first;
- }
- return p;
- }
- }
- used[v] = 2;
- deepcd[v] = deep;
- // cout << "KUKU\n";
- for (auto u: rebr[v])
- if (used[u] == 0) {
- auto [c, s] = cd(u, u, deep + 1);
- // rebrcd[c].push_back(v);
- rebrcd[v].push_back(c);
- parcd[c] = v;
- }
- return {v, subtreesize[v]};
- }
- void dfsways(int v, int to, int way = 0) {
- used[v] = deepcd[to];
- if (wayscol[to][col[v]] == 0 || wayscol[to][col[v]] > way + 1)
- wayscol[to][col[v]] = way + 1;
- if (v == to)
- used[v] = n;
- // ways[v][to] = way;
- ways[to][v] = way;
- for (auto i: rebr[v])
- if (used[i] < deepcd[to])
- dfsways(i, to, way+1);
- }
- void findways(int v) {
- dfsways(v, v);
- for (int i: rebrcd[v])
- if (deepcd[i] > deepcd[v])
- findways(i);
- }
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- freopen("centroid.in", "r", stdin);
- freopen("centroid.out", "w", stdout);
- cin >> n;
- // cout << n << "\n";
- rebr = *(new vector<vector<int>>(n));
- // par = vector<int>(n);
- // par[0] = 0;
- for (int i = 1; i < n; i++) {
- int p;
- cin >> p;
- // p--;
- // par[i] = p;
- rebr[i].push_back(p);
- rebr[p].push_back(i);
- }
- col = *(new vector<int>(n));
- for (int i = 0; i < n; i++) {
- cin >> col[i];
- }
- used = *(new vector<int>(n, 0));
- subtreesize = *(new vector<int>(n));
- dfscount(0);
- rebrcd = *(new vector<vector<int>>(n));
- parcd = *(new vector<int>(n));
- deepcd = *(new vector<int>(n));
- // cout << "qq\n";
- used = *(new vector<int>(n, 0));
- cd(0,0);
- int rootcd;
- for (int i = 0; i < n; i++)
- if (deepcd[i] == 0)
- rootcd = i;
- used = *(new vector<int>(n, -1));
- ways = *(new vector<map<int,int>>(n));
- wayscol = *(new vector<map<int,int>>(n));
- // cout << "Hi\n";
- findways(rootcd);
- // for (int i = 0; i < n; i++) {
- // for (auto [c, s] : ways[i])
- // cout << "[" << c << "," << s << "] ";
- // cout << "\n";
- // }
- //
- // for (int i = 0; i < n; i++) {
- // for (auto [c, s] : wayscol[i])
- // cout << "[" << c << "," << s << "] ";
- // cout << "\n";
- // }
- int m;
- cin >> m;
- for (int qq = 0; qq < m; qq++) {
- int v, c;
- cin >> v >> c;
- // v--;
- int res = wayscol[v][c];
- int u = v;
- while (u != rootcd) {
- u = parcd[u];
- if (wayscol[u][c] != 0 && (ways[u][v] + wayscol[u][c] < res || res == 0)) {
- res = ways[u][v] + wayscol[u][c];
- }
- }
- cout << res - 1 << " ";
- // if (res > 0)
- // cout << res - 1 << " ";
- // else
- // cout << "-1 ";
- }
- return 0;
- }
- /*
- 5
- 0 1 1 3
- 1 2 3 2 1
- 9
- 0 1
- 0 2
- 0 3
- 1 0
- 2 1
- 2 2
- 3 3
- 3 1
- 4 2
- 8
- 1 1
- 2 2
- 3 3
- 4 4
- 5 5
- 6 6
- 7 7
- 3
- 3 6
- 3 2
- 1 2
- 3
- 2
- 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement