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 N 1000005
int cnt[N],mi=2e9,ans;
vector<int> g[N];
void dfs(int s,int f,int *p){
cnt[s]=p[s];
for(auto x:g[s]){
if(x==f)continue;
dfs(x,s,p);
cnt[s]+=cnt[x];
}
}
void dfs2(int s,int f,int carry){
int m=carry;
for(auto x:g[s]){
if(x==f)continue;
dfs2(x,s,carry+cnt[s]-cnt[x]);
m=max(m,cnt[x]);
}
if(m<mi)mi=m,ans=s;
}
int LocateCentre(int n, int p[N], int s[N], int d[N]) {
int i,a,b;
for(i=0;i<n-1;i++){
a=s[i],b=d[i];
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0,-1,p);
dfs2(0,-1,0);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |