Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <queue>
- #include <ctime>
- #include <cassert>
- #include <complex>
- #include <numeric>
- #include <string>
- #include <cstring>
- #include <chrono>
- #include <random>
- #include <queue>
- #include <bitset>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<ll, int> pli;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- #define mp make_pair
- #define str(a) a.c_str()
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- const int N = 2e5;
- const int L = 17;
- const int INF = 1e9;
- vector<int> a[N];
- int col[N], mark[N];
- unordered_map <int, int> m[N];
- int n;
- vector<int> lst[N];
- int h[N], up[N][L];
- int tin[N], tout[N], ss, sz[N];
- void buildLca(int u = 0, int pr = 0, int lvl = 0) {
- tin[u] = ss++;
- h[u] = lvl;
- up[u][0] = pr;
- for (int i = 1; i < L; ++i) {
- up[u][i] = up[up[u][i - 1]][i - 1];
- }
- for (int v : a[u]) {
- if (v == pr) continue;
- buildLca(v, u, lvl + 1);
- }
- tout[u] = ss++;
- }
- bool isUpper(int a, int b) {
- return tin[a] <= tin[b] && tout[b] <= tout[a];
- }
- int getLca(int u, int v) {
- if (isUpper(u, v))
- return u;
- if (isUpper(v, u))
- return v;
- for (int i = L - 1; i > -1; --i) {
- if (!isUpper(up[u][i], v)) {
- u = up[u][i];
- }
- }
- return up[u][0];
- }
- int getDist(int a, int b) {
- return h[a] + h[b] - 2 * h[getLca(a, b)];
- }
- void reSize(int u, int p) {
- sz[u] = 1;
- for (int v : a[u]) {
- if (mark[v] || v == p) continue;
- reSize(v, u);
- sz[u] += sz[v];
- }
- }
- int findCentroid(int u, int p, int rootSize) {
- int bad = -1;
- for (int v : a[u]) {
- if (mark[v] || v == p) continue;
- if (sz[v] > rootSize / 2) {
- bad = v;
- }
- }
- if (bad == -1) {
- return u;
- }
- return findCentroid(bad, u, rootSize);
- }
- void upd(int node, int color, int lvl) {
- if (m[node].count(color) == 0) {
- m[node][color] = lvl;
- return;
- }
- m[node][color] = min(m[node][color], lvl);
- }
- void push(int u, int p, int c, int lvl) {
- lst[u].push_back(c);
- upd(c, col[u], lvl);
- for (int v : a[u]) {
- if (v == p || mark[v]) continue;
- push(v, u, c, lvl + 1);
- }
- }
- void buildCentroids(int vertex = 0) {
- reSize(vertex, vertex);
- int x = findCentroid(vertex, vertex, sz[vertex]);
- mark[x] = 1;
- lst[x].push_back(x);
- upd(x, col[x], 0);
- for (int v : a[x]) {
- if (mark[v]) continue;
- push(v, x, x, 1);
- }
- for (int v : a[x]) {
- if (mark[v]) continue;
- buildCentroids(v);
- }
- }
- int main() {
- scanf("%d", &n);
- for (int i = 1; i < n; ++i) {
- int p;
- scanf("%d", &p);
- a[p].push_back(i);
- a[i].push_back(p);
- }
- for (int i = 0; i < n; ++i) {
- scanf("%d", &col[i]);
- }
- buildLca();
- buildCentroids();
- int q;
- scanf("%d", &q);
- while (q--) {
- int v, c;
- scanf("%d %d", &v, &c);
- int res = INF;
- for (int i : lst[v]) {
- int add = INF;
- if (m[i].count(c)) {
- add = min(add, m[i][c]);
- }
- res = min(res, getDist(v, i) + add);
- }
- if (res == INF) res = -1;
- printf("%d ", res);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment