# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
805288 | 2023-08-03T14:48:36 Z | QwertyPi | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KB |
#include "traffic.h" #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 11; int p[N], sz[N]; vector<int> G[N]; void dfs(int v, int par = -1){ for(auto i : G[v]){ if(i != par){ dfs(i, v); sz[v] += sz[i]; } } sz[v] += p[v]; } void centroid(int v, int par = -1){ for(auto i : G[v]){ if(i != par && sz[i] >= (sz[0] + 1) / 2){ centroid(i, v); return; } } cout << v << endl; return; } int main() { int n; cin >> n; for(int i = 0; i < n; i++){ cin >> p[i]; } for(int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(0); centroid(0); } int LocateCentre(int N, int pp[], int S[], int D[]) { for(int i = 0; i < N - 1; i++){ G[S[i]].push_back(D[i]); G[D[i]].push_back(S[i]); } dfs(0); return centroid(0); }