| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 426606 | nots0fast | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define MAX (int)(pow(10,6) + 10)
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = pow(10,18);
ll modulo = pow(10,9) + 7;
ll dp[MAX];
vector<ll> g[MAX];
ll val[MAX];
ll par[MAX];
void dfs(ll hd, ll pr){
dp[hd] = val[hd];
par[hd] = pr;
for(auto& hr : g[hd]){
if(pr == hr){
continue;
}
dfs(hr, hd);
dp[hd] += dp[hr];
}
}
void deal(){
ll n;
cin>>n;
ll tot = 0;
fori(n){
cin>>val[i];
tot+=val[i];
}
fori(n-1){
ll ai, bi;
cin>>ai>>bi;
g[ai].pb(bi);
g[bi].pb(ai);
}
dfs(0, -1);
ll mn = inf;
ll lz = -1;
fori(n){
ll mx = tot - dp[i];
for(auto& hr : g[i]){
if(hr == par[i]){
continue;
}
mx = max(mx, dp[hr]);
}
if(mx < mn){
mn= mx;
lz = i;
}
}
cout<<lz;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
deal();
}