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>
#include "traffic.h"
using namespace std;
using ll = long long;
vector<int> v[1001001];
int n, sz[1001001];
int dfs(int u, int p){
for(auto x : v[u]) if(x != p) sz[u] += dfs(x, u);
return sz[u];
}
pair<int, int> dfs2(int u, int p){
pair<int, int> re = {n-sz[u], u};
for(auto x : v[u]) if(x != p) re.first = max(re.first, sz[x]);
for(auto x : v[u]) if(x != p) re = min(re, dfs2(x, u));
return re;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
n = N;
for(int i=0;i<N-1;i++) v[S[i]].push_back(D[i]), v[D[i]].push_back(S[i]);
dfs(0, 0);
return dfs2(0, 0).second;
}
# | 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... |