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 ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 1e5+10;
vector<int> tree[mxn];
int N;
namespace S1{
ll ans;
ll dp[mxn];
int mx[mxn];
void dfs(int now,int par){
vector<int> need;
dp[now] = 1;
for(auto nxt:tree[now]){
if(nxt == par)continue;
dfs(nxt,now);
if(dp[nxt])need.push_back(nxt);
}
if(need.size()>=2){
dp[now] = 0;
ans += need.size()*2;
for(int i = 1;i<need.size();i++){
mx[need[i-1]] = need[i];
}
mx[need.back()] = now;
mx[now] = need[0];
need.clear();
}
else if(need.size() == 1){
dp[now] = 0;
ans += 2;
int a = need[0];
mx[now] = a;
mx[a] = now;
}
if(now==par&&dp[now]){
ans += 2;
int a = tree[now][0],b = mx[a];
while(mx[b] != a)b = mx[b];
mx[now] = a;
mx[b] = now;
}
return;
}
void solve(){
dfs(1,1);
return;
}
}
namespace S2{
int mx[mxn],sz[mxn],dep[mxn];
int arr[mxn];
ll ans = 0;
void szdfs(int now,int par){
sz[now] = 1;
for(auto nxt:tree[now]){
if(nxt == par)continue;
szdfs(nxt,now);
sz[now] += sz[nxt];
}
return;
}
int get_centroid(int now,int par,int tar = sz[1]){
for(auto nxt:tree[now]){
if(nxt == par)continue;
if(sz[nxt]>(tar-1)/2)return get_centroid(nxt,now,tar);
}
return now;
}
vector<vector<int>> v;
vector<pii> vp;
void dfs(int now,int par){
dep[now] = dep[par]+1;
ans += dep[now]*2;
v.back().push_back(now);
for(auto nxt:tree[now]){
if(nxt == par)continue;
dfs(nxt,now);
}
return;
}
void solve(){
szdfs(1,1);
int cen = get_centroid(1,1);
for(auto nxt:tree[cen]){
vp.push_back({0,v.size()});
v.push_back({});
dfs(nxt,cen);
vp.back().fs = v.back().size();
}
sort(vp.begin(),vp.end());
v[0].push_back(cen);
vp[0].sc++;
int pt = 0;
while(!v.empty()){
arr[pt] = v.back().back();
v.back().pop_back();
if(v.back().empty())v.pop_back();
pt+=2;
if(pt>=N)pt = 1;
}
for(int i = 0;i<N;i++)assert(arr[i]);
for(int i = 1;i<N;i++){
mx[arr[i]] = arr[i-1];
}
mx[arr[0]] = arr[N-1];
return;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<N;i++){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
S1::solve();
S2::solve();
cout<<S1::ans<<' '<<S2::ans<<'\n';
for(int i = 1;i<=N;i++)cout<<S1::mx[i]<<' ';cout<<'\n';
for(int i = 1;i<=N;i++)cout<<S2::mx[i]<<' ';cout<<'\n';
return 0;
}
Compilation message (stderr)
Village.cpp: In function 'void S1::dfs(int, int)':
Village.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 1;i<need.size();i++){
| ~^~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:133:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
133 | for(int i = 1;i<=N;i++)cout<<S1::mx[i]<<' ';cout<<'\n';
| ^~~
Village.cpp:133:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
133 | for(int i = 1;i<=N;i++)cout<<S1::mx[i]<<' ';cout<<'\n';
| ^~~~
Village.cpp:134:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
134 | for(int i = 1;i<=N;i++)cout<<S2::mx[i]<<' ';cout<<'\n';
| ^~~
Village.cpp:134:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
134 | for(int i = 1;i<=N;i++)cout<<S2::mx[i]<<' ';cout<<'\n';
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |