#include<bits/stdc++.h>
using namespace std;
#include "traffic.h"
vector<vector<int>> g;
vector<int> subtreeSize;
void dfs(int node, int par, int p[]) {
for (int &v : g[node]) {
if (v != par) {
dfs(v, node, p);
subtreeSize[node] += subtreeSize[v];
}
}
subtreeSize[node] += p[node];
}
int centroid(int node, int par) {
for (int &v : g[node]) {
if (v != par && subtreeSize[v] >= (subtreeSize[0] + 1) / 2) {
return centroid(v, node);
}
}
return node;
}
int LocateCentre(int n, int p[], int s[], int d[]) {
g.resize(n + 1);
subtreeSize.assign(n + 1, 0);
for (int i = 0; i < n - 1; i++) {
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
dfs(0, -1, p);
for (int i = 0; i < n; i++) {
cout << subtreeSize[i] << " ";
}
return centroid(0, -1);
}
