Berland Federalization

问题要我们求的，就是怎样在树上找一个 $K$ 大小的连通子图，使得它和其它部分之间的邻边数量最少。

初步考虑这个问题，因为每个州（子图）内部要求互相连通，所以它也是一棵树，我们可以假设这个州的最高点（离根最近的点）是 $u$ ，则此州全部在 $u$ 子树里面。这样，我们可以按子树来进行DP。

定义 $\text{dp}[i][j]$ = “ $i$ 节点子树中， $i$ 被选中的情况下，共有 $j$ 个节点被选中，最小的邻边（与其它州之间的边）数量”。这样，答案就是所有节点 $\text{dp}[i][K]$ 的最小值。

状态转移( $u$ 为 $i$ 的儿子)：

\text{dp}[i][j]=\min_{u \in C_i, 0<k<j} {(\text{dp}[u][k] + \text{dp}[i][j-k]-2)}

需要 $-2$ 的原因，是加入 $u$ 之前， $(i,u)$ 这条边本来都在 $i$ 和 $u$ 的邻边集合中，加入之后就都不在了。

然后此题需要要输出最佳情况下的邻边集合，所以伴随dp，存储每个 $\text{dp}[i][j]$ 对应的邻边集合 $\text{es}[i][j]$ 。

复杂度是 $\mathcal{O}(n^3)$ .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, K;   // 400
vector<int> adj[405];
int dp[405][405];
vector<pi> es[405][405];    // edge set for each dp[][]
map<pi,int> e2i;            // map from edge to edge index, for output
const int INF = 1e9;
 
void dfs(int s, int e) {
    // initial state for dp and es
    dp[s][1] = adj[s].size();
    for (int u: adj[s])
        if (u == e)
            es[s][1].push_back({e,s});
        else
            es[s][1].push_back({s,u});
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs(u, s);
 
        for (int j = K; j >= 1; j--) {
            int mink = -1;
            for (int k = 1; k <= j; k++) {
                if (dp[u][k] == INF || dp[s][j-k] == INF) continue;
                int v = dp[u][k] + dp[s][j-k] - 2;      // -2: edge {s,u} is gone
                if (v < dp[s][j])
                    dp[s][j] = v, mink = k;
            }
            if (mink > 0) {     // merge es[u][mink] & es[s][j-mink]
                vector<pi> m;
                pi del = {s,u};
                for (auto e: es[u][mink]) if (e != del) m.push_back(e);
                for (auto e: es[s][j-mink]) if (e != del) m.push_back(e);
                es[s][j] = m;
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        e2i[{u,v}] = i+1;
    }
    for (int i = 0; i < n; i++)
        fill(dp[i], dp[i]+K+1, INF);
    dfs(0, -1);
 
    int ans = 1e9, idx;
    for (int i = 0; i < n; i++)
        if (dp[i][K] < ans)
            ans = dp[i][K], idx = i;
    printf("%d\n", ans);
    for (auto e: es[idx][K]) {
        int idx = e2i[e] ? e2i[e] : e2i[{e.second,e.first}];
        printf("%d ", idx);
    }
    return 0;
}