Submission #990699

#TimeUsernameProblemLanguageResultExecution timeMemory
990699kanphamVillage (BOI20_village)C++17
0 / 100
2 ms10584 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define pb push_back #define in insert #define fi first #define se second using namespace std; const int mod=1000000007; const int N=2e5+7; const int inf=1e17; int a[N]; int n; vector<int>dsk[N]; int d[N],dinh,h[N]; set<pii>s; void dfs0(int u,int par){ if(d[u]>d[dinh])dinh=u; s.insert({d[u],u}); for(auto v:dsk[u]){ if(v==par)continue; d[v]=d[u]+1; h[v]=h[u]+1; dfs0(v,u); } } int ans[N],kc[N]; bool ok[N]; void dfs(int u,int par){ pii cc=*s.rbegin(); s.erase(s.find(cc)); ans[u]=cc.se; ans[cc.se]=u; kc[u]=cc.fi-h[u]; kc[cc.se]=cc.fi-h[u]; ok[u]=true; ok[cc.se]=true; for(auto v:dsk[u]){ if(v==par||ok[v])continue; dfs(v,u); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; dsk[u].pb(v); dsk[v].pb(u); } dfs0(1,1); d[dinh]=0; h[dinh]=0; s.clear(); int ngu=dinh; dfs0(dinh,0); dinh=ngu; dfs(dinh,dinh); int sum=0; for(int i=1;i<=n;i++)sum+=kc[i]; cout<<sum<<'\n'; for(int i=1;i<=n;i++)cout<<ans[i]<<" "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...