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;
const int N = 1e6+7;
int n;
int sz[N];
vector<int> adj[N];
long long rans[N];
int lp[N];
bool valid[N];
int dfs(int v, int p) {
sz[v] = 1; lp[v] = 0;
for (int w : adj[v]) if (w != p) {
sz[v] += dfs(w,v);
lp[v] = max(lp[v], lp[w]+1);
}
return sz[v];
}
void dfsr(int v, int p, int len) {
rans[v] = v ? rans[p] + (n - sz[v]) - sz[v] : 0;
if (!v) for (int i = 1; i < n; i++)
rans[v] += sz[i];
int a = -1, b = -1;
a = len+1;
int max_sz = 0, llen = 0;
for (int w : adj[v]) if (w != p) {
if (sz[w] > max_sz) {
max_sz = sz[w];
llen = lp[w]+1;
}
int c = lp[w]+2;
if (c > a) swap(a, c);
if (c > b) swap(b, c);
// maintain that a>=b
}
if (n-sz[v] > max_sz) {
max_sz = n-sz[v];
llen = len;
}
for (int w : adj[v]) if (w != p)
dfsr(w,v, lp[w]+2 == a ? b : a);
if (max_sz - (n-1-max_sz) > 1)
rans[v] = -1;
else if (max_sz - (n - 1 - max_sz) == 1)
rans[v] = 2*rans[v] - llen;
else
rans[v] = 2*rans[v] - max(len, lp[v]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for (int i = 0; i < n-1; i++) {
int a, b; cin>>a>>b;
adj[--a].push_back(--b);
adj[b].push_back(a);
}
dfs(0,-1);
dfsr(0,-1, 0);
stringstream ss;
for (int i = 0; i < n; i++)
ss << rans[i] << endl;
cout << ss.str();
return 0;
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |