题目链接； HDU 4714 Tree2cycle 题意： 给一个 n 个节点和n−1条边的树。要求把这棵树变成一个环(所有的点都在环上)，每破坏一条边和新建一条边的代价都是1，求最小的代价。 数据范围： n≤106 分析： 我们来考虑保留边的最大数量，记为 left 。首先原来有 n−1 条边，保留了 left 条边，那就意味着要破坏 n−1−left 条边。要变成环的话，环上有 n 条边，所以需要新建n−left条边，总代价为：
(n−1−left)+(n−left)=2∗n−2∗left−1 显然 left 越大越好。一开始我以为 left 就是树的直径而且傻乎乎的写完交上去了，直到返回 WrongAnswer 。。。。。。其实仔细想一下就知道明显算少了。 我们可以考虑每个点的度。保留的边必须使得每个点的度小于等于2。于是我们可以定义 dp[u][0],dp[u][1],dp[u][2] 为使得以 u 为根的子树的所有节点的度小于等于2，并且 u 节点的度分别为0,1,2时保留边的最大数量。写的时候发现这样子定义不太好转移，于是放宽定义，定义 dp[u][0],dp[u][1],dp[u][2] 为使得以 u 为根的子树的所有节点的度小于等于2，并且 u 节点的度分别小于等于0,1,2时保留边的最大数量。 对于 u 的每个儿子v，都是要取 dp[v][0],dp[v][1],dp[v][2] 中的最大值。当存在 max(dp[v][0],dp[v][1])>=dp[v][2] 时，我们就可以保留 u和v 之间的边，这时统计这样的边的数量来确定 dp[u][1]和dp[u][2] 是否可以额外加1和额外加2。时间复杂度： O(n)
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; typedef long long ll; const int MAX_N = 1000010; int T, n, total; int head[MAX_N], dp[MAX_N][5]; struct Edge { int v, next; }edge[MAX_N * 2]; void AddEdge (int u, int v) { edge[total].v = v; edge[total].next = head[u]; head[u] = total++; } void dfs(int u, int p) { int flag1 = 0, flag2 = 0; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (v == p) continue; dfs(v, u); dp[u][0] += max(dp[v][0], max(dp[v][1], dp[v][2])); dp[u][1] += max(dp[v][0], max(dp[v][1], dp[v][2])); dp[u][2] += max(dp[v][0], max(dp[v][1], dp[v][2])); if(max(dp[v][1], dp[v][0]) >= dp[v][2]) { flag1++; flag2++; } } if (flag1) dp[u][1]++, dp[u][2]++; if (flag2 >= 2) dp[u][2]++; } int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); memset(head, -1, sizeof(head)); total = 0; for (int i = 1; i < n; ++i) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); AddEdge(v, u); } memset(dp, 0, sizeof(dp)); dfs (1, -1); int left = max(dp[1][0], max(dp[1][1], dp[1][2])); printf("%d\n", n * 2 - 2 * left - 1); } return 0; }