树形DP做起来很生疏，需要加强，很简单的一题做了好久。
题意也很神奇，题目中给定一棵树，要求它的最大匹配：
给出一棵有N (N<=500000)个结点的树，要求选出最多的点并且满足：
1.不包含根结点
2.每个点和它的所有儿子中只能选择一个点
输出最多能选多少个点并给一种方案。
算一题入门题吧。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500005;
int dp[maxn][2]; // 1选 0不选
int g[maxn];
struct E {
int v, next;
}e[maxn];
int tot, head[maxn];
void add(int s, int t) {
e[tot].v = t;
e[tot].next = head[s];
head[s] = tot++;
}
void init() {
tot = 0;
memset(head, -1, sizeof(head));
}
void dfs(int u) {
int i;
dp[u][1] = 1; dp[u][0] = 0;
int sum = 0, mi = maxn;
for(i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
dfs(v);
sum += dp[v][0];
if(mi > dp[v][0] - dp[v][1]) {
mi = dp[v][0] - dp[v][1];
g[u] = v;
}
}
dp[u][1] += sum;
if(sum-mi > dp[u][0]) dp[u][0] = sum-mi;
}
int ans[maxn];
void print(int u, int f) {
int i;
if(f) ans[++ans[0]] = u;
for(i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
if(f) print(v, 0);
else print(v, v==g[u]);
}
}
int main() {
int i, j, n;
scanf("%d", &n);
init();
for(i = 2; i <= n; i++) {
int x;
scanf("%d", &x);
add(x, i);
}
dfs(1);
printf("%d\n", dp[1][0]*1000);
print(1, 0);
sort(ans+1, ans+ans[0]+1);
for(i = 1; i <= ans[0]; i++)
printf("%d ", ans[i]);
puts("");
return 0;
}