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

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

反正可以直接当 \(k=3\) 去做，然后考虑直接去构造。

首先任意给树找一个根，然后将整棵树拆成几个大小为 \(\sqrt n\) 的子树，将所有这些子树的根 \(u\) 塞到一个点集 \(a\) ，然后将 \(a\) 中的点相互连接，边的数量为 \(\mathcal O(n)\)。

接着，对于点集 \(a\) 中的每个点 \(u\)，将 \(u\) 与其子树中的每个点连接，显然边数仍然为 \(\mathcal O(n)\)。

最后，再对所有子树递归这个过程即可。由于最多有 \(\mathcal O(\log \log n)\) 次递归，每次边数都是 \(\mathcal O(n)\)，因此总边数是 \(\mathcal O(n\log \log n)\) 的。

然后来证明一下为什么这样最长路径为 \(3\)，考虑两个顶点 \(u,v\) 以及它们在同一子树时的最后一次递归。令 \(c(x)\) 为与子树 \(x\) 相邻且属于 \(a\) 中的点，显然在上述构造下，若 \(c(u)\ne c(v)\)，则 \(c(u)\) 与 \(c(v)\) 一定有边直接相连。若 \(c(u)=c(v)\) 则路径更短。因此最长路径为 \(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';
}	

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';
}