树的最大独立集

题意： 对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。

Sol:树形dp

由于每个点只由其儿子或者孙子决定（二者的最大值），所以我们可以深搜一遍，回溯的时候用当前节点更新其父亲以及父亲的父亲（因为此时该节点的值已经被我们计算出来了），这种由已知贡献给未知的方法称为刷表法。

刷表法的唯一限制是，对于一个状态（记为S）所依赖的所有状态（记为S'）而言，这些状态对当前状态的贡献必须是独立的。（即S'是互相独立的）

如此可以写出DP。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 105, maxm = maxn * 2;

int n, tot;

int fa[maxn][25], s[maxn], gs[maxn], h[maxn], d[maxn];

struct edge
{
    int v, next;
}a[maxm];

void add(int x, int y)
{
    a[tot].v = y;
    a[tot].next = h[x];
    h[x] = tot++;
}

void dfs(int u, int fat)
{
    for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i -1]][i - 1];
    for (int i = h[u]; ~i; i = a[i].next)
    {
        int v = a[i].v;
        if (v == fat) continue;
        fa[v][0] = u;
        dfs(v, u);
    }
    d[u] = max(s[u], gs[u] + 1);//此时d[u]的值已经被计算出来了。
    s[fa[u][0]] += d[u];//贡献给父亲
    gs[fa[u][1]] += d[u];//贡献给父亲的父亲
}

int main()
{
    freopen("最大独立集.in","r",stdin);
    scanf("%d", &n);
    tot = 0; memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1, 0);
    printf("%d", d[1]);
    return 0;
}

另外，uva1220还要求给出当前最优解是否唯一，这个貌似也要用dp做，之后补坑。