DP in Tree

一开始学dfs的时候,觉得那就是递归了.

而后在第一学期期末机考的时候扑街在那道递归题目上,

寒假花了一个上午努力做出来,

兴奋之余并没有意识到其实那道题就有记忆化搜索的意味.

树形DP就是一个dfs+DP的特例,最开始想刷这个是源自于4+2参考书上一道题的完全没有看懂,于是觉得有必要去学一下,找到了下面这篇博客刷题参考然后埋头开刷, 大概期末考试断断续续一个星期, 刷了其中一些比较简单的题, 完全没有达到一开始4+2那题的难度.

东西都写在一个文档里面typora已经处理艰难,所以先将这篇文章发出来(刚刚发现是因为CF那道题的处理上发生了bug,删去了那段之后应该能愉快地继续使用了)

相对概括一些说,它需要找到一个节点和树上其它节点(或者边)之间的关系,然后进行一遍或者两边的搜索.

明天就是4+2了,与大家共勉

yali_漆子超论文笔记

ps: 这里只有第一篇的题解.

  • 树的重心 删去后结点最多的树的个数最小

    • 定理: 存在一个点使得分出来的子树的结点个数均不大于N/2

    • 定理二: 如果一颗树中每个点的度<=D 那么存在一条边使得分出来的两颗子树结点个数在$[\frac{N}{D+1},\frac{ND}{D+1}]$ => D为常数时基于边的分治递归最坏深度为logN

    • 所谓重心，就是删掉此结点后，剩下的结点最多的树结点个数最小。

      每次分治，我们首先算出重心，为了计算重心，需要进行两次dfs，第一次把以每个结点为根的子树大小求出来，第二次是从这些结点中找重心
      其实POJ3107那里有重心的代码.

poj 2342 Anniversary party

不能选相邻的.记得f[n][1] = max(f[m][0],f[m][1])就可以

poj2196 树上距离每个点最远距离

Input file contains multiple test cases

  • 核心思想(三种方法) : 两遍DFS

  • 方法: 记录每棵树根往下最大和第二大,两遍dfs分别更新往下的max和往下的max

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35

    void dfs(int v,int dep)
    {
        vis[v] = dep;
        for (int i = 0; i < e[v].size(); i++) {
            int u = e[v][i].to;
            if (!vis[u]) {
                dfs(u,dep+1);
                int nt = dp[u][0] + e[v][i].len;
                if (nt > dp[v][1]) {
                    dp[v][1] = nt;
                    if (nt > dp[v][0]) {
                        dp[v][1] = dp[v][0];
                        dp[v][0] = nt;
                    }
                }//保留最大和第二大的子树最远节点
            }
        }
    };

    void dfs1(int v)
    {
        vis[v] = 1;
        for (int i = 0; i < e[v].size(); i++) {
            int u = e[v][i].to;
            if (!vis[u]) {
            //一个树上最远的节点,要么是两个最远的子树节点,要么是最远兄弟节点+1
                if (dp[v][0] == dp[u][0] + e[v][i].len) {
                    dp[u][2] = max(dp[v][2], dp[v][1]) + e[v][i].len;
                }else
                    dp[u][2] = max(dp[v][2], dp[v][0]) + e[v][i].len;
                dfs1(u);
            }
        }
    }

    ​

  • 方法2

    首先任意一次dfs求出树上最长直径的一个端点End,然后以该端点为起点再次dfs求出另一个端点，然后再次以求出的另一个端点为起点dfs,每次做dfs的时候都更新dist[]（dist[u]表示u到树上任意节点的最远距离），可以证明树上任意某个节点到树上任意节点的最远距离的端点一定会是树上直径的两个端点之一。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

    void dfs(int v,int fa,int len)
    {
        if(len > max_len) 
           End = v,max_len = len;
        for (int i = 0; i < e[v].size(); i++) {
            int nt = e[v][i].to,w = len + e[v][i].len;
            if (nt != fa) {
                dfs(nt, v, w);
                dp[nt] = max(dp[nt],w);
            }
        }
    }//v是当前节点,len是到现在节点的距离,dp[nt]表示的是现在点最远的子树距离

    dfs(1,-1,0);     //第一遍随意扫一遍,知道一个直径端点
    dfs(End, -1, 0); //第二遍从一个端点开始扫一遍,知道另一个端点
    dfs(End, -1, 0); //用另一个端点更新每个点的最远距离(前面两次也有更新)

    ​

  • (A了,没注意多重数据)自己不能理解为啥错了(有可能是写崩了)的方法_留在这里

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32

    void dfs(int v,int dep)
    {
        vis[v] = dep;
        for (int i = 0; i < e[v].size(); i++) {
            int u = e[v][i].to;
            if (!vis[u]) {
                dfs(u,dep+1);
                update(dp[v][0],dp[u][0] + e[v][i].len);
            }
        }
    };//只记录往下的最大值  dp[i][0]

    void dfs1(int v)
    {
        for (int i = 0; i < e[v].size(); i++) {
            int u = e[v][i].to;
            if (vis[u] == vis[v] + 1) {
                int oth = 0;
                for (int j = 0; j < e[v].size(); j++) {
                    int p = e[v][j].to;
                    if (vis[p] == vis[u] && p != u) {
                        update(oth, e[v][j].len + dp[p][0]);
                    }
                }
                if(v != 1)
                    update(oth, dp[v][1]);
                dp[u][1] = oth + e[v][i].len;
                dfs1(u);
            }
        }
    }//然后枚举     dp[i][1] = max(1.父节点向上 2.父到兄弟 + 兄向下) +到父亲距离

##CF219D 求根集

题目是给一张边有向的树形图。要选出首都的点，首都要都能走到其他点，因此要反转一些边的方向。问可以选哪几个点作为首都，使它们所需反转边的数量最少。

O(n)两遍DFS

  • 将要翻转的边赋值为1,不需要的边赋值为0,就是统计了
  • 一遍向下统计以该节点为根的变化量
  • 一遍向上统计它往上走的变化量
  • 最后求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void dfs0(int u,int fa){
    for(int i=head[u]; i!=-1; i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        dfs0(v,u);
        d[0][u]+=d[0][v]+edge[i].w;
    }
}//by 题解博客
void dfs1(const int &fr,int v)
{
    for (int i = 0; i < e[v].size(); i++) {
        int u = e[v][i];
        if (u != fr) {
            dp[u][1] = dp[v][1] + dp[v][0] - dp[u][0] + 1;
   		//父节点向上 + 父节点向下 - 当前节点向下 + 当前边反向的差 
            dfs1(v, u);
        }
    }
    for (int i = 0; i < re[v].size(); i++) {
        int u = re[v][i];
        if (u != fr) {
            dp[u][1] = dp[v][1] + dp[v][0] - dp[u][0] - 1;
            dfs1(v, u);
        }
    }
}//向上DP

DP思想: 有向图两边同时展开,看利用情况

POJ1741

1
2
3
4
5
6
while(i < j) //经典  
{  
    while(dis[i] + dis[j] > k && i < j) j--;  
        ret += j - i;  
    i++;  
}

期末附加题

  • 给一棵树,问能不能两两节点配对完
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <vector>
#include <cstdio>
using namespace std;

const int maxn = 10000 + 5;
vector<int> e[maxn];
int paired[maxn];//存储是否配对成功
int n,a,b,flag;//个数,两个临时变量,YES

inline void dfs(const int pos,const int fa)
{
    if (flag == 0) return;//错误状态
    for (int i = 0; i < e[pos].size(); i++) {
        int nt = e[pos][i];
        if (nt != fa) {
            dfs(nt, pos);//测试下一个配对情况
            if (flag == 0) return;
        }
    }
    if (paired[pos] == false) {
        if (fa < 0 || paired[fa] == 1 ) {
            flag = 0;//已经被配对,出现错误状态
        }else
            paired[fa] = paired[pos] = 1;
    }
}

POJ1155 背包i 最多节点

给一颗树,叶节点是客户,其它所有是中转站,求不亏损的情况下的最多客户

第一个树形背包参考

对于每一个节点的子节点向上进行优化

这道题而言,就是每完成一次对于子节点的递归之后就回来优化根节点的状态

  1. 状态定义为dp[i][j]表示第i个节点得到j个顾客的时候的最大获益
  2. num数组优化剪枝
  3. 防错temp数组(存前)
  4. 初始化的时候因为有负数,将
    1. dp[i][0] = 0
    2. dp[i][1] = (i > n + m)?val : -inf (因为后面的是有价值节点)
    3. dp[i][oth] = -inf
    4. num[i] = 0
  • 关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void dfs(int pos)
{
    for (int i = 0; i < e[pos].size(); i++) {
        int nt = e[pos][i].t,ct = e[pos][i].w;//下一个节点以及花费
        dfs(nt);
        memcpy(temp, dp[pos], sizeof(dp[pos]));//保存当前的值,防止背包使用更改的值
        for (int j = 0; j <= nums[pos] ; j++) {//父节点已有情况
            for (int k = 0; k <= nums[nt]; k++) {//子节点已有情况
                update(dp[pos][k+j],
                       temp[j] + dp[nt][k] - ct);//背包,看子节点的k个顾客能否优化父节点sum-k=j个的情况
            }
        }
        nums[pos] += nums[nt];//优化搜索空间,保存当前最多搜索的东西
    }
}
		//最后输出
		for (int i = m; i>=0; i--) 
        {
            if (dp[1][i] >= 0)
            {
                cout << i << endl;
                break;
            }
        }

HDU 1011_1561 背包ii 取父才取子

1011给一颗树,每个节点都有花费和获得

想要拿子节点的东西必须先拿父节点的

1561较难抽象成树,但更好解决 (是1011的一个cost == 1特例)

  • 注意在m=0的时候输出0,不然会挂?==

  • 关键代码分析(1011)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void dfs(int pos,const int fa)
    {
      //这里dp的状态是,不少于i个的时候能获得的量,那么初始化就是把cost后的都赋值为earn
        for (int j = bugs[pos]; j <= m; j++)
            dp[pos][j] = posi[pos];//posi[pos]就是当前节点能获得的量(下面就不用搜以上了)
      //利用子树进行背包优化
        for (int i = 0; i < e[pos].size(); i++) {
            int nt = e[pos][i];
            if(nt == fa) continue;
            dfs(nt, pos);
          	
            //从大到小背包,防止重复(因为是往上dp所以这样不会) 
            for (int j = m; j >= bugs[pos]; j--)
              	//父节点花费(bugs[pos],而且已经获得了posi[pos](最开始的赋值..))
              	//所以不能取到 j - bugs[pos] 以上,  	
                for (int k = 1; k <= j - bugs[pos]; k++) 
                  	update(dp[pos][j],dp[nt][k] + dp[pos][j-k];
        }
    }

POJ1974 背包iii

给一颗树,求最少删去多少条边能得到大小为p的子树

一开始思路不知道挂在哪里了,三遍dfs把自己搞晕

参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int dp[maxn][maxn];//以a为根size为b的最小子树删边
vector<int>chi[maxn],fa[maxn];

/*只遍历一次,因为是一棵树,所以对于每个节点的处理只有一次
	1. 初始化,对于每个节点所有size都是不可以到达的,inf
	2. size为1是子树本身,0
	3. 对于每一个子树节点,有两种选择
		a. 割去子树节点,也就是 b == 0 当前 = dp[p][a] + 1;
		b. 不割去子树,用子树size更新 也就是 b != 0 的时候,用dp[p][a-b] + dp[nt][b]更新dp[p][a]
	4. 由于对当前dp没有后效性,所以不需要temp数组
	5. 然后最后在dfs外层扫一遍所有的P节点删去数,如果不是根节点,需要+1(因为删上面)
	6. 好像发现自己懵逼在哪了......因为它只能保留子树,所以兄弟似乎不影响...往下看就行
	*/
void solve(int p)
{
  	fill(dp[p], dp[p] + maxn, inf);
    dp[p][1] = 0;
    for (int i = 0; i < chi[p].size(); i++) {
        int nt = chi[p][i];
        solve(nt);
        for (int a = N; a >= 1; a--) //被更新的size
            for (int b = 0; b < a; b++) //子树size
                if (b) 
                    update(dp[p][a], dp[p][a-b] + dp[nt][b]);
                else
                    dp[p][a] = dp[p][a] + 1;
    }
}

HDU3586,切断根与叶子最小边权

给每一条边边权,求切断根和所有叶子的最小花费

哦对了,所有删去边权的和<m

.

为啥DP

一开始瞄了一眼别人题解..想了很久都没明白一些人题解里面干嘛要背包……

然后就直接二分强行做dfs了..WA了几发之后发现弄混淆了两个概念

  1. 删去该节点的和
  2. 删去该节点的最小边权

于是折腾了一会后发现,只有记忆化搜索才能优化

但是记忆化太麻烦了,不如开一个dp数组

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int pos,int mp)
{
    if(e[pos].empty()) dp[pos] = inf;
    for (int i = 0; i < e[pos].size(); i++) {
        int nt = e[pos][i].to,ct = e[pos][i].ct;
        dfs(nt, mp);
        if (ct > mp) {
            dp[pos] += dp[nt];
        }else
            dp[pos] += min(dp[nt],ct);//当前边权可以与子树边权共同优化
    }
}//dp[i]是i为根cost

为啥二分

二分的原因是,这玩意是一个<m存在性问题,那么符合单调性

1
2
3
4
5
6
7
8
9
10
while (l <= r) {
         int mid = l + (r-l)/2;
         memset(dp, 0, sizeof(dp));  
         dfs(1, mid);
         if (dp[1] <= m) {
             ans = mid;
             r = mid - 1;
         }else
             l = mid + 1;
     }//对于整数的二分模板.

POJ3107 树的重心

重心就是使得 (最大的子树) 最小的根

O(n)的算法是假设第一个点为根
dfs统计每棵树的子树大小.

然后那个点最大的子树就是$max(n - sub - 1,max(sub))$
这道题挺无聊的在于..坑vector/deque,
参考网上代码发现,得写邻接表才能避免TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

const int maxn = 50000 + 5;
int n,a,b,mt;
int cnt[maxn],tot[maxn];

struct edge{
    int to,nt;
}e[maxn * 2];

int size = 0,head[maxn];
int ans[maxn],pos;

inline void update(int &a,const int &b)
{
    if(b > a) a = b;
}

inline void update1(int &a,const int &b)
{
    if(b < a) a = b;
}

void addEdge(int u,int v)
{
    e[size].to = v;
    e[size].nt = head[u];
    head[u] = size++;
}

int dfs(const int &p,const int &fa)
{
    tot[p] = 1;
    
    for (int i = head[p]; i != -1; i = e[i].nt) {
        int nt = e[i].to;
        if(nt == fa) continue;
        tot[p] += dfs(nt, p);
    }
    cnt[p] = n - tot[p];
    for (int i = head[p]; i != -1; i = e[i].nt) {
        int nt = e[i].to;
        update(cnt[p], tot[nt]);
    }
    update1(mt, cnt[p]);
    return tot[p];
}

本文标题:DP in Tree

文章作者:Renld

发布时间:2016年06月25日 - 19时15分

最后更新:2016年07月12日 - 11时25分

原始链接:http://renld.github.io/2016/06/25/treeDP/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. yali_漆子超论文笔记
  2. 2. poj 2342 Anniversary party
  3. 3. poj2196 树上距离每个点最远距离
  4. 4. POJ1741
  5. 5. 期末附加题
  6. 6. POJ1155 背包i 最多节点
  7. 7. HDU 1011_1561 背包ii 取父才取子
  8. 8. POJ1974 背包iii
  9. 9. HDU3586,切断根与叶子最小边权
    1. 9.1. 为啥DP
    2. 9.2. 为啥二分
  10. 10. POJ3107 树的重心