思路

首先考虑如何判断一个答案是否可行。

设我们现在判断答案为 $x$ 是否合法，我们可以从下往上做，每次将最深的点拿出来，此时的操作应该是其 $x-1$ 级祖先向根节点连边，这样这一整颗子树都是合法的，删掉这个子树。

重复上述过程 $k$ 次后判最深的点是否和根的距离小于等于 $x$，即为 $x$ 是否合法。

将这棵树拍到 DFS 序上，用线段树维护最深的点，删子树可以变成一个区间减 $\infin$。这一部分的时间复杂度为 $O(k\log n)$。

考虑换根怎么做。首先线段树上维护的是每个点到深度的距离，设当前的根为 $u$，换根后为 $v$，只需要将 $v$ 子树内到根的距离减一，$v$ 子树外到根的距离加一，这个也是容易维护的。

接下来就剩下树上 $k$ 级祖先和换根后的子树，这个比较经典，分讨就可以了。

具体的，以 $rt$ 为根，$u$ 的树上 $k$ 级祖先可以如下分讨（记 $u$ 和 $rt$ 在原树上的 lca 为 $l$）：

1. 若 $\operatorname{dis}(u,l)\ge k$，则 $u$ 的树上 $k$ 级祖先为原树上的 $k$ 级祖先；
2. 否则，则 $u$ 的树上 $k$ 级祖先为原树上 $rt$ 的 $\operatorname{dis}(u,rt)-k$ 级祖先。

以 $rt$ 为根，$u$ 的子树为：

1. $rt=u$，此时 $u$ 的子树为所有点；
2. 原树中，$rt$ 在 $u$ 的子树内，设 $v$ 为 $rt\to u$ 路径上倒数第二个点，此时 $u$ 的子树为除原树中 $v$ 的子树以外的所有点；
3. 否则，$u$ 的子树不变。

对于每个点都二分一下可以做到 $O(nk\log^2n)$，精细实现可以通过。

但是还可以做到更优。发现换根后答案的变动不会超过 $1$，可以将 $O(\log n)$ 次判断缩到 $O(1)$ 次，此时时间复杂度为 $O(nk\log n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5+5,inf = 2e9;
int n,k,typ;
vector<int> g[N];
int sz[N],son[N],top[N],f[N],dep[N],dfn[N],idx,pre[N];
void dfs1(int u,int fa)
{
	sz[u] = 1,dep[u] = dep[fa]+1,f[u] = fa;
	for(auto v:g[u])
	{
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u] = v;
	}
}
void dfs2(int u,int tp)
{
	top[u] = tp,pre[dfn[u] = ++idx] = u;
	if(!son[u]) return;
	dfs2(son[u],tp);
	for(auto v:g[u])
	{
		if(v==son[u]||v==f[u]) continue;
		dfs2(v,v);
	}
}
inline int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x = f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
inline int jump(int x,int k)//k 级祖先 
{
	if(k>=dep[x]) return -1;
	while(1)
	{
		if(dep[x]-dep[top[x]]>=k) return pre[dfn[x]-k];
		k-=dep[x]-dep[top[x]]+1,x = f[top[x]];
	}
}
inline int jump2(int x,int y)//x 到 y 路径上倒数第二个点 
{
	while(1)
	{
		if(dep[top[x]]<=dep[y]) return son[y];
		if(f[top[x]]==y) return top[x];
		x = f[top[x]];
	}
}
struct node{
	pair<int,int> res;
	int tag; 
}t[N<<2];
#define ls (k<<1)
#define rs (k<<1|1)
#define pushup(k) (t[k].res = max(t[ls].res,t[rs].res))
inline void add(int k,int v){t[k].res.x+=v,t[k].tag+=v;}
inline void down(int k)
{
	if(!t[k].tag) return;
	add(ls,t[k].tag),add(rs,t[k].tag);
	t[k].tag = 0;
}
void build(int k,int l,int r)
{
	if(l==r) return t[k].res = {dep[pre[l]],pre[l]},void();
	int mid = (l+r)/2;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(k);
}
void change(int k,int l,int r,int x,int y,int v)
{
	if(l>y||r<x) return;
	if(l>=x&&r<=y) return add(k,v);
	int mid = (l+r)/2;
	down(k);
	change(ls,l,mid,x,y,v),change(rs,mid+1,r,x,y,v);
	pushup(k);
}
pair<int,int> p[N];int cnt;
inline bool chk(int x,int rt)
{
	while(cnt)
	{
		change(1,1,n,p[cnt].x,p[cnt].y,inf);
		cnt--;
	}
	for(int i = 1;i<=k;i++)
	{
		auto _ = t[1].res;
		int u = _.second,d = _.first;
		if(d<=x+1) return 1;
		int l = lca(u,rt),v;
//		求 u 的 x-1 级祖先 v 
		if(dep[u]-dep[l]>=x-1) v = jump(u,x-1);
		else v = jump(rt,dep[rt]+dep[u]-2*dep[l]-(x-1));
//		删掉 v 的子树
		if(rt==v) change(1,1,n,1,n,-inf),p[++cnt] = {1,n};//这种情况不可能出现 
		else if(dfn[v]<=dfn[rt]&&dfn[rt]<dfn[v]+sz[v])
		{
			int vv = jump2(rt,v);
			change(1,1,n,1,dfn[vv]-1,-inf),p[++cnt] = {1,dfn[vv]-1};
			change(1,1,n,dfn[vv]+sz[vv],n,-inf),p[++cnt] = {dfn[vv]+sz[vv],n};
		}
		else change(1,1,n,dfn[v],dfn[v]+sz[v]-1,-inf),p[++cnt] = {dfn[v],dfn[v]+sz[v]-1};
	}
	auto _ = t[1].res;
	int u = _.second,d = _.first;
	return d<=x+1;
}
int ans[N];
void dfs3(int u,int fa,int now)
{
	if(u!=1)
	{
		if(!chk(now,u)) now++;
		else if(now>1&&chk(now-1,u)) now--;
		ans[u] = now;
	}
	for(auto v:g[u])
	{
		if(v==fa) continue;
		change(1,1,n,1,n,1);
		change(1,1,n,dfn[v],dfn[v]+sz[v]-1,-2);
		dfs3(v,u,now);
		change(1,1,n,1,n,-1);
		change(1,1,n,dfn[v],dfn[v]+sz[v]-1,2);
	}
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k>>typ;
	for(int i = 1,u,v;i<n;i++)
		cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
	dfs1(1,0),dfs2(1,1);
	build(1,1,n);
	int l = 1,r = n,res = 0;
	while(l<=r)
	{
		int mid = (l+r)/2;
		if(chk(mid,1)) res = mid,r = mid-1;
		else l = mid+1;
	}
	cout<<res<<' ';
	if(typ)
	{
		dfs3(1,0,res);
		for(int i = 2;i<=n;i++) cout<<ans[i]<<' ';
	}
	return 0;
}