# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
448573 | Deepesson | 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>
#define MAX 1210000
typedef std::pair<long long,long long> pii;
std::vector<long long> con[MAX];
long long res = 2e9+10;
long long ind;
int* pop;
long long dfs(long long pos,long long prev,long long dist){
long long max = dist;
long long soma = pop[pos];
for(auto&x:con[pos]){
if(x!=prev){
long long r = dfs(x,pos,dist+(long long)pop[pos]);
max=std::max(max,r);
soma+=r;
}
}
if(max<res){
res=std::min(res,max);
ind=pos;
}
return soma;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
pop=pp;
for(auto&x:con)x.clear();
res=2e9+10;
for(int i=0;i!=N-1;++i){
con[S[i]].push_back(D[i]);
con[D[i]].push_back(S[i]);
}
int start = 0;
for(int i=0;i!=N;++i)if(con[i].size()==1)start=i;
dfs(start,-1,0);
return ind;
}
static int N,P[1000000],S[1000000],D[1000000];
int main(){
int i;
scanf("%d",&N);
for (i=0;i<N;i++) scanf("%d",&P[i]);
for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
int r = LocateCentre(N,P,S,D);
printf("%d\n",r);
return 0;
}