#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll=long long;
using pii=array<int,2>;
using tii=array<int,3>;
using ti4=array<int,4>;
const int N=105;
int n,vis[N],sz[N];
vector<int> g[N],ans[2][N];
void dfsSize(int u,int p){
sz[u]=1;
for(int v: g[u]) if(p!=v&&!vis[v]){
dfsSize(v,u);
sz[u]+=sz[v];
}
}
int findCentroid(int u,int p,int S){
for(int v: g[u]) if(p!=v&&!vis[v]&&sz[v]>=S) return findCentroid(v,u,S);
return u;
}
int p[N][N];
vector<int> C[N];
void initPar(int u,int r){
for(int v: g[u]) if(p[r][u]!=v&&!vis[v]){
p[r][v]=u;
initPar(v,r);
}
}
int solve(int u){
dfsSize(u,0);
u=findCentroid(u,0,(sz[u]+1)/2);
initPar(u,u);
vis[u]=1;
vector<int> V;
for(int v: g[u]) if(!vis[v]) V.push_back(solve(v));
for(int v: V){
int w=v;
while(u!=w){
w=p[u][w];
for(int x: C[v]){
ans[0][x].push_back(w);
ans[0][x].push_back(w);
ans[1][x].push_back(ans[1][x].back());
ans[1][x].push_back(w);
}
}
}
C[u].push_back(u);
for(int v: V) for(int w: C[v]) C[u].push_back(w);
int t=2;
for(int v: C[u]) t=max(t,(int)ans[0][v].size());
t=(t+1)/2*2;
for(int v: C[u]) while((int)ans[0][v].size()<t){
ans[0][v].push_back(u);
ans[1][v].push_back(u);
}
return u;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int u,v,i=1;i<n;i++){
cin>>u>>v;
u++; v++;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
solve(1);
cout<<ans[0][1].size()<<"\n";
for(int i=1;i<=n;i++){
for(int x: ans[0][i]) cout<<x-1<<" ";
assert(ans[0][i].size()==ans[0][1].size());
for(int x: ans[0][i]) assert(1<=x&&x<=n);
cout<<"\n";
}
for(int i=1;i<=n;i++){
for(int x: ans[1][i]) cout<<x-1<<" ";
assert(ans[1][i].size()==ans[0][1].size());
for(int x: ans[1][i]) assert(1<=x&&x<=n);
cout<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
For some pair of nodes Ondrej and Edward do not meet each other |
| 2 |
Halted |
0 ms |
0 KB |
- |
