Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <functional>
- #include <set>
- #include <map>
- #include <math.h>
- #include <cmath>
- #include <string>
- #include <time.h>
- #include <random>
- #include <unordered_set>
- #include <unordered_map>
- #include <bitset>
- #include <string.h>
- #include <stack>
- using namespace std;
- //
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- #define cin in
- #define cout out
- #define pii pair<int,int>
- #define ll long long
- #define db double
- #define ld long double
- #define uset unordered_set
- #define umap unordered_map
- #define F first
- #define S second
- #define vec vector
- #define ms multiset
- #define pb push_back
- #define pll pair<ll,ll>
- #define pdd pair<ld, ld>
- #define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define pnn pair<Node*, Node*>
- #define uid uniform_int_distribution
- ifstream in("input.txt");
- ofstream out("output.txt");
- const int MAX_N = 1e5;
- int n, cl[MAX_N], t_sz[MAX_N];
- vector<int> g[MAX_N];
- bool used[MAX_N];
- void input() {
- cin >> n;
- for (int i = 0; i < n - 1; i++) {
- int a;
- cin >> a;
- a--;
- g[i].push_back(a);
- g[a].push_back(i);
- }
- for (int i = 0; i < n; i++)
- cin >> cl[i];
- }
- vector<int> cent[MAX_N];
- int get_size(int v, int p) {
- t_sz[v] = 1;
- for (int to : g[v]) {
- if (!used[to] && to != p)
- t_sz[v] += get_size(to, v);
- }
- return t_sz[v];
- }
- int get_cent(int v, int p, int sz) {
- for (int to : g[v]) {
- if (!used[to] && to != p && 2 * t_sz[to] >= sz)
- return get_cent(to, v, sz);
- }
- used[v] = 1;
- return v;
- }
- void process(int v, int p, int cent) {
- }
- void build(int v) {
- v = get_cent(v, -1, get_size(v, -1));
- }
- int main() {
- input();
- memset(used, 0, sizeof(used));
- }
- /*
- Для каждого центроида найдём расстояние до каждой вершины в его компоненте
- N logN
- map<int, int> dist;
- Мин расстояние от центроида до вершины каждого из цветов в каждом центроиде
- N logN
- map<int, int> dist_cl;
- Для каждой вершины храним список центроидов, в компоненты которых она входит
- N logN
- vector<int> cent[MAX_N];
- */
Advertisement
Add Comment
Please, Sign In to add comment