Submission #518654

#TimeUsernameProblemLanguageResultExecution timeMemory
518654ac2huUntitled (POI11_ins)C++14
0 / 100
557 ms131076 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 10; vector<int> adj[N]; int n; int mx[N], nodes[N], total_subtree[N], full_total[N], ans[N]; struct LCA{ int n,l,timer; vector<int> tin, tout,dist; vector<vector<int>> up; LCA(int root,int siz){ n = siz; timer = 0; l = ceil(log2(n)); tin.resize(n); tout.resize(n); dist.resize(n,0); up.assign(n,vector<int>(l + 1)); dfs0(root,root); } void dfs0(int v, int p){ tin[v] = ++timer; up[v][0] = p; for (int i = 1; i <= l; ++i){ up[v][i] = up[up[v][i-1]][i-1]; } for (int u : adj[v]) { if (u != p){ dist[u] = dist[v] + 1; dfs0(u, v); } } tout[v] = ++timer; } // Check if u is ancestor of v bool is_ancestor(int u,int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; } // Find LCA of u and v int lcaquery(int u,int v){ if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = l; i >= 0; --i) { if (!is_ancestor(up[u][i], v)) u = up[u][i]; } return up[u][0]; } int distance(int u,int v){ int ll = lcaquery(u,v); return dist[u] + dist[v] - 2*dist[ll]; } }; void dfs(int i,int p){ for(auto e : adj[i]){ if(e == p)continue; mx[e] = mx[i] + 1; dfs(e,i); } } void dfs1(int i,int p){ nodes[i] = 1; total_subtree[i] = 0; for(int e : adj[i]){ if(e == p)continue; dfs1(e,i); nodes[i] += nodes[e]; total_subtree[i] += total_subtree[e] + nodes[e]; } } void dfs2(int i,int p){ int mx = n - nodes[i]; for(int e : adj[i]){ if(e == p)continue; full_total[e] = full_total[i] - nodes[e] + n - nodes[e]; dfs2(e,i); mx = max(mx, nodes[e]); } if(mx >= n - mx) ans[i] = -1; } signed main() { iostream::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); cin >> n; for(int i = 0;i<n - 1;i++){ int a,b;cin >> a >> b; a--;b--; adj[a].push_back(b); adj[b].push_back(a); } LCA lc(0,n + 1); pair<int,int> dia; dia.first = max_element(lc.dist.begin(),lc.dist.end()) - lc.dist.begin(); dfs(dia.first,-1); dia.second = max_element(mx, mx + n) - mx; for(int i =0;i<n;i++){ mx[i] = max(lc.distance(i,dia.first), lc.distance(i,dia.second)); } dfs1(0,-1); full_total[0] = total_subtree[0]; dfs2(0,-1); // for(int i = 0;i<n;i++) // cout << full_total[i] << " "; // cout << "\n"; for(int i = 0;i<n;i++){ if(ans[i] != -1){ ans[i] = 2*full_total[i] - mx[i]; } } for(int i = 0;i<n;i++) cout << ans[i] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...