Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <list>
- #include <unordered_map>
- #include <unordered_set>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef string str;
- //typedef __int128 ultraint;
- #define endl "\n"
- #define sqrt sqrtl
- #define F first
- #define S second
- #define all(vc666) vc666.begin(), vc666.end()
- #define pow binpow
- //#define Vec Point
- const ll inf = (ll)1e18 + 7;
- ld EPS = 1e-9;
- ld Pi = 3.1415926535897932384;
- ll binpow(ll a, ll n) {
- ll res = 1;
- while (n) {
- if (n & 1) {
- res *= a;
- }
- a *= a;
- n >>= 1;
- }
- return res;
- }
- struct Node {
- unordered_map<ll, ll> colors;
- };
- struct Node_help {
- vector<ll> colors;
- };
- const ll sz1 = 1e5;
- const ll sz2 = 17;
- vector <Node_help> centroid_build_vertex;
- vector <Node> centroid_vertex;
- vector <ll> g[sz1];
- ll cl[sz1];
- ll d[sz1];
- pair <ll, ll> ti[sz1];
- ll up[sz1][sz2 + 1];
- void dfs2(ll v, ll p, ll& time) {
- ti[v].first = time++;
- if (p == -1) {
- d[v] = 0;
- up[v][0] = 0;
- }
- else {
- d[v] = d[p] + 1;
- up[v][0] = p;
- }
- for (ll i = 1; i <= sz2; i++) {
- up[v][i] = up[up[v][i - 1]][i - 1];
- }
- for (auto& u : g[v]) {
- if (u != p) {
- dfs2(u, v, time);
- }
- }
- ti[v].second = time++;
- }
- bool pred(ll a, ll b) {
- return ti[a].first <= ti[b].first && ti[a].second >= ti[b].second;
- }
- ll lca(ll a, ll b) {
- if (pred(a, b)) {
- return a;
- }
- for (ll i = sz2; i >= 0; i--) {
- if (!pred(up[a][i], b)) {
- a = up[a][i];
- }
- }
- return up[a][0];
- }
- ll get_dist(ll a, ll b) {
- ll sup = lca(a, b);
- return d[a] + d[b] - 2 * d[sup];
- }
- struct Centroid_decomposition {
- vector<vector<ll>> gr;
- vector<ll> tree, siz;
- ll root = -1;
- Centroid_decomposition(ll n) {
- tree.resize(n, -2);
- siz.resize(n);
- }
- void sizes(ll v, ll p) {
- siz[v] = 1;
- for (ll& u : g[v]) {
- if (u != p && tree[u] == -2) {
- sizes(u, v);
- siz[v] += siz[u];
- }
- }
- }
- ll centroid(ll v, ll p, ll s) {
- for (ll& u : g[v]) {
- if (u != p && tree[u] == -2 && siz[u] > s / 2) {
- return centroid(u, v, s);
- }
- }
- return v;
- }
- void build(ll v, ll p) {
- sizes(v, -1);
- tree[v] = p;
- if (p != -1) {
- gr[v].push_back(p);
- gr[p].push_back(v);
- }
- centroid_build_vertex[v].colors.push_back({ v });
- for (ll& u : g[v]) {
- if (tree[u] == -2) {
- build(centroid(u, -1, siz[u]), v);
- }
- }
- for (ll& u : gr[v]) {
- if (u != p) {
- if ((ll)centroid_build_vertex[v].colors.size() < centroid_build_vertex[u].colors.size()) {
- centroid_build_vertex[v].colors.swap(centroid_build_vertex[u].colors);
- }
- for (ll& i : centroid_build_vertex[u].colors) {
- centroid_build_vertex[v].colors.push_back(i);
- }
- centroid_build_vertex[u].colors.clear();
- }
- }
- gr[v].clear();
- for (ll& i : centroid_build_vertex[v].colors) {
- ll x = get_dist(i, v);
- if (centroid_vertex[v].colors.find(cl[i]) == centroid_vertex[v].colors.end()) {
- centroid_vertex[v].colors[cl[i]] = x;
- continue;
- }
- centroid_vertex[v].colors[cl[i]] = min(centroid_vertex[v].colors[cl[i]], x);
- }
- }
- void build_tree() {
- ll v = 0;
- sizes(v, -1);
- gr.resize(tree.size());
- centroid_build_vertex.resize(tree.size());
- centroid_vertex.resize(tree.size());
- build(centroid(v, -1, siz[v]), -1);
- gr.clear();
- siz.clear();
- }
- };
- ll get(ll v, ll color, Centroid_decomposition& U) {
- ll ans = inf;
- ll v2 = v;
- while (v2 != -1) {
- auto& clrs = centroid_vertex[v2].colors;
- auto it_c = clrs.find(color);
- if (it_c != clrs.end()) {
- ans = min(ans, (it_c->second) + get_dist(v, v2));
- }
- v2 = U.tree[v2];
- }
- if (ans == inf) {
- ans = -1;
- }
- return ans;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- ll t = 1;
- //cin >> t;
- while (t--) {
- ll n, i, j, x, y, q, timer = 1, root;
- cin >> n;
- for (i = 1; i < n; i++) {
- cin >> j;
- g[j].push_back(i);
- g[i].push_back(j);
- }
- for (i = 0; i < n; i++) {
- cin >> cl[i];
- }
- dfs2(0, -1, timer);
- centroid_vertex.resize(n);
- centroid_build_vertex.resize(n);
- Centroid_decomposition U(n);
- U.build_tree();
- cin >> q;
- while (q--) {
- cin >> i >> j;
- cout << get(i, j, U) << ' ';
- }
- cout << endl;
- }
- //Deisgned by skimono
- }
- //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement