Warning: mysqli_query(): (HY000/1021): Disk full (/tmp/#sql_51b_2.MAI); waiting for someone to free some space... (errno: 28 "No space left on device") in /opt/lampp/htdocs/wordpress/wp-includes/wp-db.php on line 2033
CF1423C Duan’s Railway(CF1423C Duan’s Railway)-ai – 知识波

# CF1423C Duan’s Railway(CF1423C Duan’s Railway)-ai

## CF1423C Duan’s Railway(CF1423C Duan’s Railway)

int n,k;
int vis[11111],viss[11111],siz[11111];
vector<int>e[11111],st,at;
vector<pair<int,int> >ans;
void dfs3(int u,int n)
{
vis[u]=1;
for(int v:e[u]) if(!vis[v]&&!viss[v])
{
dfs3(v,n);
siz[u]+=siz[v];
}
if(siz[u]>=n)
{
viss[u]=1;
siz[u]=0;
at.emplace_back(u);
}
}
void dfs2(int u)
{
st.emplace_back(u);
vis[u]=1;
for(int v:e[u]) if(!vis[v]&&!viss[v]) dfs2(v);
}
void dfs1(int u)
{
st.clear();
dfs2(u);
int sz=st.size();
int sz2=floor(sqrt(sz));
for(int x:st) vis[x]=0,siz[x]=1;
if(sz<=4)
{
for(int x:st) viss[x]=1;
return;
}
at.clear();
dfs3(u,sz2);
for(int x:st) vis[x]=0;
for(int x:at) for(int y:at) if(x<y)
{
ans.emplace_back(x,y);
}
vector<int>st2=st;
for(int x:at)
{
st.clear();
dfs2(x);
for(int y:st)
{
if(x!=y) ans.emplace_back(x,y);
vis[y]=0;
}
}
for(int x:st2) if(!viss[x]) dfs1(x);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
R(i,1,n-1)
{
int x,y;
cin>>x>>y;
e[x].emplace_back(y);
e[y].emplace_back(x);
}
dfs1(1);
cout<<ans.size()<<'\n';
for(auto [x,y]:ans) cout<<x<<" "<<y<<'\n';
}

————————

When \ = 3 can be constructed directly, then \ = 3 can be considered directly.

First, find a root for the tree arbitrarily, then split the whole tree into several sub trees with the size of \ (\ sqrt n \), plug the roots \ (U \) of all these sub trees into a point set \ (a \), and then connect the points in \ (a \) with each other, and the number of edges is \ (\ mathcal o (n) \).

Next, for each point \ (U \) in the point set \ (a \), connect \ (U \) with each point in its subtree. Obviously, the number of sides is still \ (\ mathcal o (n) \).

Finally, this process can be recursive for all subtrees. Since there are at most \ (\ mathcal o (\ log \ log n) \) recursions, and the number of edges each time is \ (\ mathcal o (n) \), the total number of edges is \ (\ mathcal o (n \ log \ log n) \).

Then let’s prove why the longest path is \ (3 \), considering two vertices \ (U, V \) and their last recursion in the same subtree. Let \ (C (x) \) be a point adjacent to the subtree \ (x \) and belonging to \ (a \). Obviously, under the above construction, if \ (C (U) \ ne C (V) \), then \ (C (U) \) and \ (C (V) \) must have an edge directly connected. If \ (C (U) = C (V) \), the path is shorter. Therefore, the longest path is \ (3 \).

int n,k;
int vis[11111],viss[11111],siz[11111];
vector<int>e[11111],st,at;
vector<pair<int,int> >ans;
void dfs3(int u,int n)
{
vis[u]=1;
for(int v:e[u]) if(!vis[v]&&!viss[v])
{
dfs3(v,n);
siz[u]+=siz[v];
}
if(siz[u]>=n)
{
viss[u]=1;
siz[u]=0;
at.emplace_back(u);
}
}
void dfs2(int u)
{
st.emplace_back(u);
vis[u]=1;
for(int v:e[u]) if(!vis[v]&&!viss[v]) dfs2(v);
}
void dfs1(int u)
{
st.clear();
dfs2(u);
int sz=st.size();
int sz2=floor(sqrt(sz));
for(int x:st) vis[x]=0,siz[x]=1;
if(sz<=4)
{
for(int x:st) viss[x]=1;
return;
}
at.clear();
dfs3(u,sz2);
for(int x:st) vis[x]=0;
for(int x:at) for(int y:at) if(x<y)
{
ans.emplace_back(x,y);
}
vector<int>st2=st;
for(int x:at)
{
st.clear();
dfs2(x);
for(int y:st)
{
if(x!=y) ans.emplace_back(x,y);
vis[y]=0;
}
}
for(int x:st2) if(!viss[x]) dfs1(x);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
R(i,1,n-1)
{
int x,y;
cin>>x>>y;
e[x].emplace_back(y);
e[y].emplace_back(x);
}
dfs1(1);
cout<<ans.size()<<'\n';
for(auto [x,y]:ans) cout<<x<<" "<<y<<'\n';
}