题意：给一棵无向图构成的树，要求删除一些边，再添加一些边。使得图中每个点直接和其它两个点相连并且保证所有点是连通的。求至少要经过几次操作才能满足题意，每次操作为删除一条边或者增加一条边。
解法：分析可得，要满足题意，那么最后生成的图肯定是所有点连成一个环。并且原图中保留的边越多，那么添加的边就越少。假设原图有N个点，保留了X条边，那么最终的结果就是 (N-X)*2-1，所以求出最大的X就求出了结果。
定状态：dp[x][0]为根节点为x的子树，其中x不和其父节点相连，能保留的边的最大数量；
dp[x][1]为根节点为x的子树，其中x和其父节点相连，能保留的边的最大数量。
在原树中DP即可求得最大的X。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>#define ll long longusing namespace std;const int N = 50;
vector<int> G[N];
int n, dp[N][N];class RoadsReorganization {
public:int MaxKeep(int x, bool c, int f) {int &res = dp[x][c];if (res != -1) return res;int sum = 0;for (int i = 0; i < G[x].size(); i++) {int y = G[x][i];if (y != f)sum += MaxKeep(y, 0, x);}res = sum;for (int i = 0; i < G[x].size(); i++) {int y = G[x][i];if (y == f) continue;res = max(res, sum - MaxKeep(y, 0, x) + MaxKeep(y, 1, x) + 1);}if (c) return res;for (int i = 0; i < G[x].size(); i++) {int y = G[x][i];if (y == f) continue;for (int j = i + 1; j < G[x].size(); j++) {int z = G[x][j];if (z == f) continue;res = max(res, sum - MaxKeep(y, 0, x) - MaxKeep(z, 0, x) +MaxKeep(y, 1, x) + MaxKeep(z, 1, x) + 2);}}return res;}int minDaysCount(vector<string> kingdom) {n = kingdom.size();for (int i = 0; i < n; i++) G[i].clear();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (kingdom[i][j] == '1')G[i].push_back(j);}}memset(dp, -1, sizeof(dp));return (n - MaxKeep(0, 0, -1)) * 2 - 1;}
};