# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
373308 | 2021-03-04T04:45:14 Z | No_Ice | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long const int mxN = 1e6; const ll INF = 1e17; int N; vector<int> adj[mxN]; ll fans[mxN]; ll ans = INF; ll dfs(int u, int p = -1) { ll sum = 0; for (int v : adj[u]) { if (v != p) { ll c_sum = 0; c_sum += fans[v]; c_sum += dfs(v, u); sum = max(sum, c_sum); } } return sum; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i=0; i < N; i++) { cin >> fans[i]; } for (int i=0; i < N-1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int ans1 = 0; for (int i=0; i < N; i++) { ll temp = dfs(i); if (temp < ans) { ans = temp; ans1 = i; } } cout << ans1 << '\n'; return 0; }