注意到划分完这棵树以后，每条连通块之间的边的一端一定相同，且是大小为 \(k\) 的连通块。
于是考虑这个连通块的最高点，设 \(f(i,j)\) 为 \(i\) 点所在连通块大小为 \(j\) 时所需的最小边数。
令 \(f'(i)\) 为原来的 \(f(i)\)。
对于 \(i\) 的每个 \(s\in son(i)\)，枚举从 \(s\) 来的连通块大小进行转移：
\(f(i,j)=\max_{w=0}^{\min(j-1,sz_s)}f(s,w)+f'(i,j-w)\)。
复杂度 \(O(n^3)\)。
初始值为 \(f(i,1)=0\)。
边界为 \(f(i,sz_i)=0,f(i,0)=1\)。（dp结束后赋值）
\(f(i,0)=1\) 是因为这个点的子树一定不会被选，先把和父亲的边算上，后面不需要特判。
考虑怎么求具体方案：设 \(g(i,j)\) 为 \(f(i,j)\) 的方案，每次更新 \(f(i,j)\) 后再更新 \(g(i,j)\)。
设 \(f(i,j)=f'(i,k)+f(s,j-k)\)，则 \(g(i,j)=g'(i,k)+g(s,j-k)+[j=k](edge(i,s))\)，\(g\) 的加法表示答案拼接，后面特判和子树断开要加边的情况。
\(g\) 更新 \(O(n^2)\) 次，每次 \(O(n)\)，复杂度 \(O(n^3)\)。
于是直接 dp 就好了。注意树形 dp 时注意 \(sz\) 的更新，否则复杂度就错了。
总复杂度 \(O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 405;
int f[N][N], sz[N], k, ans = 1e9, idx;
vector<int> g[N][N];
int fst[N], nxt[N << 1], to[N << 1], h = 2, fid[N];
inline void add(int x, int y) {nxt[h] = fst[x], fst[x] = h, to[h] = y, h ++;}
void dfs(int x, int fa)
{
f[x][1] = 0;
sz[x] = 1;
for(int e = fst[x], i = to[e]; e; e = nxt[e], i = to[e])
{
if(i == fa) continue;
fid[i] = e / 2;
dfs(i, x);
sz[x] += sz[i];
for(int j = sz[x]; j >= 0; j --)
{
int fnow = 1e9, id = -1;
for(int k = 0; k <= min(j, sz[i]); k ++)
{
fnow = min(fnow, f[x][j - k] + f[i][k]);
if(fnow == f[x][j - k] + f[i][k]) id = k;
}
g[x][j] = g[x][j - id];
if(!id) g[x][j].push_back(e / 2);
else g[x][j].insert(g[x][j].end(), g[i][id].begin(), g[i][id].end());
f[x][j] = fnow;
}
}
f[x][0] = 1;
f[x][sz[x]] = 0;
ans = min(ans, f[x][k] + !!fa);
if(f[x][k] + !!fa == ans) idx = x;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n; cin >> n >> k;
memset(f, 0x3f, sizeof f);
for(int i = 1; i < n; i ++)
{
int x, y; cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(1, 0);
cout << ans << "\n";
if(fid[idx]) g[idx][k].push_back(fid[idx]);
sort(g[idx][k].begin(), g[idx][k].end());
for(int i : g[idx][k]) cout << i << " ";
return 0;
}