树形dp

树形dp

树形dp的性质：没有环，dfs不会重复，而且具有明显而又严格的层数关系。

判断一道题是否是树形dp：首先判断数据结构是否是一棵树，然后是否符合动态规划的要求。如果都符合，那么是一道树形dp的问题。我们需要通过下面几个步骤来解题。

1.建树

建树过程中，我们需要通过数据量和题目的要求，选择合适的树的存储方式。

一般来说，如果节点数小于5000，我们一般可以用邻接矩阵来存储。如果节点数更多，我们一般采用邻接表来存储。（注意，采用邻接表时，我们需将边开到2*n,因为边是双向）。如果是二叉树或则多叉树转二叉树，我们可以用一个brother[]、child[]来存储。

2.写出树规方程

通过观察孩子与父亲之间的关系建立方程。通常我们认为，树形DP的写法有两种：

1：根到叶子：不过这种动态规划在实际问题中运用的不多。

2：叶子到根：即根的子节点传递有用的信息给根，之后根得出最优解。

注意：上面两种方法一般来说是不能相互转换的（个别情况是个例），且第二种方法适用的普遍性广泛很多。

3.入门例题

1：poj 2342

问题描述：对于一棵树，每个节点有自己的权值，取了一个节点其相邻的父节点和子节点就没有价值了。求最大价值。

分析可得状态转移方程：当取 i 节点时：(dp[i][1]+=dp[j][0])；当不取 i 节点时：(dp[[i][0]+=max(dp[j][1],dp[j][0]))；上面的 j 都表示为节点 i 的下属。

show code:

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 1e4 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int h[maxn], n;
struct edge{
    int nex, to;
}Edge[maxn];
int head[maxn], tot, vis[maxn], rt;
int f[maxn][2];

inline void add(int from, int to){
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    head[from] = tot; 
}
void dfs(int u)
{
    f[u][0] = 0;
    f[u][1] = h[u];
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] = max(f[u][1], f[u][1] + f[v][0]);
    }
}

int main()
{
    scanf("%d", &n);
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; ++i){
        scanf("%d", &h[i]);
    }
    for(int i = 1; i < n; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        add(y, x);  vis[x] = 1;
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]) {rt = i; break;}
    }
    dfs(rt);
    printf("%d
", max(f[rt][0], f[rt][1]));
}

2：POJ 1947

题意：有n个点组成的树，问至少删除多少条边才能获得一颗有p个节点的子树。

我们定义状态dp[i][j]表示以 i 为根节点生成节点数为 j 的最少删的边的个数，所以我们可以得到状态转移方程：

[dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[i.son][k]-2) ]

上面的 -2 表示

#include <bits/stdc++.h>

using namespace std;
const int maxn=200;
const int inf=0x3f3f3f3f;
int dp[maxn][maxn];     //dp[i][j]代表以i为根节点，生成节点数为k所删掉的边
int a,b,n,p,root;       //分别代表边的两个端点，边的总数，最后要得到的边的数量，根节点
int fa[maxn];
vector<int> tree[maxn];
void dfs(int x)
{
    int len=tree[x].size();
    for(int i=0;i<len;++i)      //不能从1到Len，因为vector数组下标是从0开始的
    {
        dfs(tree[x][i]);     //递归子节点
        for(int j=p;j>1;j--)    //j=1情况下面已近初始化过了
            for(int k=1;k<j;++k)
                dp[x][j]=min(dp[x][j],dp[x][j-k]+dp[tree[x][i]][k]-2);
    }
}

int main()
{
    ios::sync_with_stdio(false);

    memset(fa,false,sizeof(fa));
    cin>>n>>p;
    for(int i=1;i<n;++i){
        cin>>a>>b;
        tree[a].push_back(b);
        fa[b]=a;
    }
    root=1;
    while(fa[root])     //找根节点
        root=fa[root];
    for(int i=1;i<=n;++i)   //初始化dp
    {
        //以i为根，生成节点数为1的子树所需删掉的根，每个节点都有个父节点+1，根节点也有个虚拟父节点，方便处理
        dp[i][1]=tree[i].size()+1;          //这里也是为什么下面状态转移时要-2的原因了
        for(int j=2;j<=p;++j)
            dp[i][j]=inf;
    }
    dfs(root);
    dp[root][p]--;              //将根节点的虚拟节点删去
    int res=inf;
    for(int i=1;i<=n;++i)
        res=min(res,dp[i][p]);
    cout<<res<<endl;

    system("pause");
    return 0;
}

3.换根树形dp poj-3585

换根dp一般是遍历两次无根树中的所有结点，第一次随便以一个点作为根自下而上跑一次树形dp, 第二次则还以刚刚那个点作为根节点，自上而下的找到以另外一点为根的权值和原来的树形dp跑出的权值之间的关系，对于每个点O(1)换根。故时间复杂度为O(n)。

题意：树的每条边有自己的权值，以哪个结点作为源点使得总权值最大（如果一个结点有多个节点，只能取最小的）

1：O(n^2)的做法

直接上状态转移方程：

[g[root]=sum_{son∈son(root)}left{ egin{aligned} v(root,son) size(son)=1\ min(g[son],v) size(son)>1\ end{aligned} ight. ]

每一个点按照上面方法做一遍树形dp即可。

2：O(n)的做法

由于这是一颗无根树，不同的根会产生不同的答案，故我们只需思考一下如何进行换根。而换根的主要思路就是如何处理根与根的转化。

设f[i]表示以 i 为根的子树中，答案的最大值，g[i]表示以 i 为根节点的到子端点的最大流量。所以有状态转移方程：

[f[i] =left{ egin{aligned} v(i,j) size(j)=1\ g[j]+min(v(i,j),f[i]-min(g[j],v(i,j))) size(j)>1\ end{aligned} ight. ]

show code:

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 10;

struct edge{
    int nex, to, val;
}Edge[maxn<<1];
int head[maxn], tot;
int n, de[maxn], f[maxn], dis[maxn];

inline void init()
{
    tot = 0;
    for(int i = 1; i <= n; ++i){
        dis[i] = de[i] = 0;
        head[i] = -1;
    }
}
inline void add(int from, int to, int val){
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    Edge[tot].val = val;
    head[from] = tot;
}
void dp(int u, int fa)         //树形dp， 自下而上
{
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(fa == v) continue;
        dp(v, u);
        if(de[v] == 1)  dis[u] += Edge[i].val;          //一定要注意边界条件！
        else dis[u] += min(Edge[i].val, dis[v]);
    }
}   
void dfs(int u, int fa)         //换根， 每个点O(1)换根, n割点O(n)
{
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(fa == v) continue;                           //找到新根与原来的dis之间的关系
        if(de[u] == 1)  f[v] = Edge[i].val + dis[v];
        else f[v] = dis[v] + min(Edge[i].val, f[u] - min(Edge[i].val, dis[v]));
        dfs(v, u);
    }
}

int main()
{
    int t; scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        init();
        for(int i = 1; i < n; ++i){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            add(a, b, c), add(b, a, c);
            de[a]++, de[b]++;
        }
        int rt = 1;             //随便选一个点作为根节点做一下树形dp
        dp(rt, -1);    f[1] = dis[1];
        dfs(rt, -1);            //再利用刚刚那个根堆每个点换一下根
        int ans = 0;
        for(int i = 1; i <= n; ++i){
            ans = max(ans, f[i]);
        }
        printf("%d
", ans);
    }
}