poj1947

树状dp,不简单。

题意：给出一棵有根树，问最少切断几条边可以得到有i个结点的子树（连通分支）。

采用左儿子右兄弟的存储方式，

dp用两个数组：

f[i][j]表示以i为根的子树，形成以本子树根结点为根（不包含本子树以外结点），共j个结点的子树所需的最小消耗。这里并没有计算切断i与其父亲连接的边的消耗。

g[i][j]表示以i节点的父亲为根的，i结点以及i的父亲的子结点链中的i以后的结点做根的子树，构成共j个结点的以i的父亲为根（不包含本子树以外结点）的子树所需的最小消耗（i的兄弟们在形成子树时与i的父亲相连，即计算消耗时无需切断与i父亲的连接,但j个结点中不包含i的父亲）

有状态转移方程：g[root][count] = min(g[tree[root].next][count - i] + f[root][i], g[root][count]);

f[root][count +1] = g[tree[root].son][count];

我们只需要把f[i][0]初始化为1，就可以直接把切断整个以root为根的子树的情况融合在状态转移方程中了。意思就是在以root为根的子树中取0个点，需要切断与root的连接，消耗1。

用递归的方法来填写两个数组。可以形象地认为最外层循环是枚举count,对于每个count，对树进行从下到上，对子树链进行从右到左的填写。

其实用记忆化搜索的方式会更简便易懂。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
usingnamespace std;

#define maxn 155
#define inf 0x3f3f3f3f

struct Node
{
    int son, next, father, num;
} tree[maxn];

int n, p, root;
int f[maxn][maxn], g[maxn][maxn];

void work(int root, int count)
{
    if (root ==0)
        return;
    work(tree[root].son, count);
    work(tree[root].next, count);
    g[root][count] = inf;
    if (tree[root].next)
        for (int i =0; i <= count; i++)
            g[root][count] = min(g[tree[root].next][count - i] + f[root][i],
                    g[root][count]);
    else
        g[root][count] = f[root][count];
    f[root][count +1] = inf;
    if (count +1> tree[root].num)
        return;
    f[root][count +1] = g[tree[root].son][count];
}

void cal(int root)
{
    if (root ==0)
        return;
    cal(tree[root].son);
    cal(tree[root].next);
    int temp = tree[root].son;
    tree[root].num =1;
    while (temp)
    {
        tree[root].num += tree[temp].num;
        temp = tree[temp].next;
    }
}

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d%d", &n, &p);
    memset(tree, 0, sizeof(tree));
    for (int i =0; i < n -1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        tree[b].next = tree[a].son;
        tree[a].son = b;
        tree[b].father = a;
    }
    for (int i =1; i <= n; i++)
        if (tree[i].father ==0)
        {
            root = i;
            break;
        }
    cal(root);
    for (int i =1; i <= n; i++)
        f[i][0] =1;
    for (int i =0; i < p; i++)
        work(root, i);
    int ans = inf;
    for (int i =1; i <= n; i++)
        if (i == root)
            ans = min(ans, f[i][p]);
        else
            ans = min(ans, f[i][p] +1);
    printf("%d\n", ans);
    return0;
}