题目

{% fold 点击显/隐题目 %}

有一个n个节点n-1条边组成的树。 每个点看成一个人，连接u和v的边看成是“中意关系”，即u和v两个人都想和对方组队。每个人希望组队的对象有可能有多个。 一支队伍由且仅由两个人组成，并且如果u和v组队了，那么u、v将不能和其他人再组成一支队。 现在问你，这n个人最多能组成多少支队伍。（允许某些人组不了队） 一种可行的组队方案： 1与3组队 4与5组队 最多组成2支队
第一行输入一个整数n,m(1<=n<=200000) 接下来n-1行，每行两个整数u,v，表示u和v两个人都想和对方组队。 数据保证是一个合法的树。
输出一个整数，表示最多能组成多少支队伍。
5 1 2 1 3 2 4 4 5
2
{% endfold %}

题解

下意识写了匈牙利算法,不过这道题会爆时间
再仔细看一下题目
可以发现其实求树上父节点和子节点配对能配多少对
可以用动态规划求解

用dp[t][0]表示编号为t的节点往下并且不选取节点t能达到的最多对数
用dp[t][1]表示编号为t的节点往下并且选取节点t能达到的最多对数

很容易就可以发现 dp[t][0] = sum{ max(dp[child][0], dp[child][1])) }
而 dp[t][1] 则根据是否存在没有选取的子节点(上一步有使用dp[child][0])有dp[t][1] = dp[t][0] 和 dp[t][1] = dp[t][0] + 1

代码

{% fold 点击显/隐代码 %}```cpp 组队分配 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
using namespace std;

const int maxn = 200005;

vector e[maxn];
int n;
int parent[maxn];
int dp[maxn][2];

void init() {
memset(parent, 0, (n + 5) * sizeof(int));
for (int i = 0; i <= n; ++i)
e[i].clear();
}

void addEdge(int u, int v) {
e[u].push_back(v);
e[v].push_back(u);
}

void dfs(int t) {
// printf("dfs(%d)\n", t);
dp[t][0] = dp[t][1] = 0;
bool emptyChild = false;
for (auto child : e[t]) {
if (parent[t] != child) {
parent[child] = t;
dfs(child);
if (dp[child][0] < dp[child][1]) {
dp[t][0] += dp[child][1];
} else {
emptyChild = true;
dp[t][0] += dp[child][0];
}
}
}
dp[t][1] = dp[t][0] + emptyChild;
// printf("dp[%d]={%d,%d}\n", t, dp[t][0], dp[t][1]);
}

int main() {
while (~scanf("%d", &n)) {
init();
for (int i = 1; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
addEdge(a, b);
}
dfs(1);
printf("%d\n", max(dp[1][0], dp[1][1]));
}
return 0;
}

{% endfold %}