SCHeng
首页 归档 Feed

树形DP

2020-07-23 dp algorithmanddatastruct algorithmquiz

普通树形DP

2019湖南邀请赛 I Neko and tree

P2016 战略游戏 树形 DP 入门

题解

1
2
dp[u][0] += dp[to][1];
dp[u][1] += min(dp[to][1], dp[to][0]);

[HAOI2009]毛毛虫 题解

对任意一条链，「链上的节点」和「与该链直接相连且不在链上的节点」构成一条「毛毛虫」。 求树上「毛毛虫」节点数的最大值。

参考

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 300010;

struct node
{
    int to, next;
} e[maxn<<1];
int head[maxn<<1], tot;
int size[maxn], ans;

void add(int u, int v )
{
    e[++tot] = node{v, head[u]};
    head[u] = tot;
}

void dfs1(int from, int fa )
{
    int deg = 0;
    int sizei, sizej;
    sizei = sizej = 0;
    //printf("%d %d\n", from, fa);
    for ( int i = head[from]; i; i = e[i].next )
    {
        deg ++;
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs1(to, from);
        sizei = max(sizei, size[to]);
    }
    if ( deg == 1 ) size[from] = sizei + 1;
    else size[from] = sizei + deg - 1;
}

void dfs2(int from, int fa )
{
    int deg = 0;
    int sizei, sizej;
    sizei = sizej = 0;
    for ( int i = head[from]; i; i = e[i].next )
    {
        deg ++;
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs2(to, from);
        if ( size[to] > sizei ) { sizej = sizei; sizei = size[to]; }
        else if ( size[to] > sizej ) sizej = size[to];
    }
    if ( sizei == 0 ) ans = max( ans, deg + 1 );
    else if ( sizej == 0 ) ans = max( ans, sizei + deg );
    else ans = max(ans, sizei + sizej + deg - 1);
}

void dfs3(int from, int fa )
{
    int deg = 0;
    int sizei, sizej;
    sizei = 0, sizej = 0;
    for ( int i = head[from]; i; i = e[i].next  )
    {
        deg ++;
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs3(to, from);
        if ( size[to] > sizei ) { sizej = sizei; sizei = size[to]; }
        else if ( size[to] > sizej ) sizej = size[to];
    }

    if ( sizei == 0 ) ans = max( ans, deg + 1 );
    else if ( sizej == 0 ) ans = max( ans, sizei + deg );
    else ans = max(ans, sizei + sizej + deg - 1);

    if ( deg == 1 ) size[from] = sizei + 1;
    else size[from] = sizei + deg - 1;
}

int main()
{
    ans = 0;
    scanf("%d %d", &n, &m);
    int from, to;
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d %d", &from, &to);
        add(from, to);
        add(to, from);
    }
    /*dfs1(1, 0);
    dfs2(2, 0);*/
    dfs3(1, 0);
    printf("%d\n", ans);

    return 0;
}

[JSOI2015]salesman 题解

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
// 注意分析多种情况出现时子树的形状
using namespace std;

const int maxn = 100010;
const int INF = 0x3f3f3f3f;

struct node
{
    int to, next;
} e[maxn<<1];

int head[maxn], tot, n;
int times[maxn], val[maxn];
int f[maxn], flag = 0;

void add(int u, int v)
{
    e[++tot] = node{v,head[u]};
    head[u] = tot;
}

void dfs( int u, int fa )
{
    priority_queue<int> q;
    for ( int i = head[u]; i; i = e[i].next )
    {
        int to = e[i].to;
        if ( to == fa ) continue;
        dfs(to, u);
        q.push(f[to]);
    }
    int cnt = 0, jil = INF; 
    int xx;
    if ( q.size() >= 2 )
    {
        xx = q.top();q.pop();
        jil = q.top();q.push(xx);
    }
    while ( !q.empty() )
    {
        cnt ++;
        xx = q.top();
        if ( xx == 0 || ( times[u] == cnt && jil == xx ) ) flag = 1;
        if ( xx < 0 || times[u] + 1 == cnt  ) break;
        f[u] += xx;
        jil = xx;
        q.pop();
    }
}

int main()
{
    scanf("%d", &n);
    for ( int i = 2; i <= n; i ++ ) scanf("%d", &val[i]);
    for ( int i = 2; i <= n; i ++ ) 
    {
        scanf("%d", ×[i]);
        times[i] --;
    }
    dfs(1, 0);
    times[1] = INF;val[1] = 0;
    int from, to;
    for ( int i = 1; i <= n - 1; i ++ )
    {
        scanf("%d %d", &from, &to);
        add(from, to);
        add(to, from);
    }
    for ( int i = 1; i <= n; i ++ ) f[i] = val[i];
    dfs(1, 0);
    //for ( int i = 1; i <= n; i ++ )
    printf("%d\n", f[1]);
    if ( flag )  printf("solution is not unique\n");
    else printf("solution is unique\n");
    return 0;
}

[POI2014]FAR-FarmCraft

题解 dp[u]为以u为根的树,每个人装好电脑且遍历完的时间(不包括回来) g[u]为以u为根的树,遍历(一次)完的时间 dp[u]-g[u]为等待时间,且从大到小排序,因为一棵树的总操作时间取决于这棵树的所有子树中操作时间最长的那一棵

转移方程: dp[u] = max(dp[u], dp[sons] + g[u] + 1); g[u] += (g[sons] + 2); 可以认为dp[sons]是进入子树,g[u]是从子树回来,加一是从 u 到 sons.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
    #include <bits/stdc++.h>

using namespace std;

const int maxn = 500010;

struct node
{
    int to, next;
} e[maxn<<1];

int n;
int c[maxn], head[maxn], tot;
int dp[maxn], g[maxn];

void add( int u, int v )
{
    e[++tot] = node{v,head[u]};
    head[u] = tot;
}

bool cmp(int a, int b)
{
    return dp[a] - g[a] >  dp[b] - g[b] ;
}

void dfs(int u, int fa)
{
    if (u != 1) dp[u] = c[u];
    vector<int> son;
    for (int i = head[u]; i; i = e[i].next)
    {
        int to = e[i].to;
        if ( to == fa ) continue;
        son.push_back(to);
        dfs(to, u);
    }
    sort(son.begin(), son.end(), cmp);
    for (auto ite : son)
    {
        int sons = (int) ite;
        dp[u] = max(dp[u], dp[sons] + g[u] + 1);
        g[u] += (g[sons] + 2);
    }

}

int main()
{
    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    int from, to;
    for ( int i = 1; i <= n - 1; i ++ )
    {
        scanf("%d %d", &from, &to);
        add(from, to);
        add(to, from);
    }
    dfs(1, 0);
    printf("%d\n", max(dp[1], g[1] + c[1]));
    return 0;   
}

换根树形DP

模板 [POI2008]STA-Station

题解

f[i]为以i为根时，深度的最大和 f[v] = f[u] - size[v] * 2 + n由于从u转移到v，v的所有子节点深度都减少了1就有-size[v]，然后u的所有子结点深度加了1那么就有+n-size[u]。 只要先dfs一次将size和dep计算出，再dfs求dp转移就好了。 f[e[i].to] = f[u] - size[e[i].to] * 2 + n;

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

struct node 
{
    int to, next;
} e[1000010<<1];
int head[1000010<<1],tot;

void add(int u, int v)
{
    e[++tot] = node{v, head[u]};
    head[u] = tot;
}

long long n, size[1000010], dep[1000010];
long long f[1000010];

void dfs(int u, int fa)
{
    size[u] = 1;
    dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        if (e[i].to != fa)
        {
            dfs(e[i].to, u);
            size[u] += size[e[i].to];
        }
    }
}

void get_ans(int u, int fa)
{
    for (int i = head[u]; i; i = e[i].next)
    {
        if (e[i].to != fa)
        {
            f[e[i].to] = f[u] - size[e[i].to] * 2 + n;
            get_ans(e[i].to, u);
        }
    }
}

int main()
{
    scanf("%lld", &n);
    int u, v;    
    for (int i = 1; i <= n - 1; i ++)
    {
        scanf("%d %d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; i ++) f[1] += dep[i];
    get_ans(1,1);
    long long int ans = -1;
    int id;
    for (int i = 1; i <= n; i ++) 
    {
        if (f[i] > ans)
        {
            ans = f[i];
            id = i;
        }
    }
    printf("%d\n", id);
    return 0;
}

CF1092 F. Tree with Maximum Cost 上一题的带点权版 题解

转移方程：f[v] = f[u] + sum -size[v] * 2; d[u] += (d[v] + size[v]);计算有深度的点权乘积和

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;

typedef long long ll;

struct node 
{
    int to, next;
} e[maxn<<1];
int tot, head[maxn<<1];
ll n, val[maxn], sum;
ll d[maxn], size[maxn];
ll f[maxn];

void add(int u, int v)
{
    e[++tot] = node{v, head[u]};
    head[u] = tot;
}

void dfs(int u, int fa)
{
    size[u] = val[u];
    for (int i = head[u]; i; i = e[i].next )
    {
        int v = e[i].to;
        if (v != fa)
        {
            dfs(v, u);
            size[u] += size[v];
            d[u] += (d[v] + size[v]);
        }
    }
}

void get_ans(int u, int fa)
{
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v != fa)
        { 
            f[v] = f[u] + sum -size[v] * 2;
            get_ans(v, u);
        }
    }
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i ++) 
    {
        scanf("%lld", &val[i]);
        sum += val[i];
    }
    int x, y;
    for (int i  = 1; i <= n - 1; i ++)
    {
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1,0);
    // printf("f1 = %lld\n", f[1]); 
    f[1] = d[1];
    get_ans(1,0);
    ll ans = -1;
    for (int i = 1; i <= n; i ++) ans = max(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}

Great Cow Gathering G

题解

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 200010;
const ll INF = 1e55;


struct node 
{
    ll to, next, w;
} e[maxn<<1];

int tot, head[maxn<<1];
ll n, val[maxn], sum;
ll d[maxn], size[maxn];
ll f[maxn];

void add(ll u, ll v, ll w)
{
    e[++tot] = node{v, head[u], w};
    head[u] = tot;
}

void dfs(int u, int fa)
{
    size[u] = val[u];
    for (int i = head[u]; i; i = e[i].next )
    {
        ll v = e[i].to;
        if (v != fa)
        {
            dfs(v, u);
            size[u] += size[v];
            d[u] += (d[v] + size[v] * e[i].w);
        }
    }
}

void get_ans(int u, int fa)
{
    if (u == 1) f[u] = d[u];
    for (int i = head[u]; i; i = e[i].next)
    {
        ll v = e[i].to;
        if (v != fa)
        { 
            f[v] = f[u] + (sum -size[v]) * e[i].w - size[v] * e[i].w;
            get_ans(v, u);
        }
    }
}

int main()
{
    scanf("%lld", &n);
    sum = 0;
    for (int i = 1; i <= n; i ++) 
    {
        scanf("%lld", &val[i]);
        sum += val[i];
    }
    ll x, y, z;
    for (int i  = 1; i <= n - 1; i ++)
    {
        scanf("%lld %lld %lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    dfs(1,1);
    // printf("f1 = %lld\n", f[1]); 
    f[1] = d[1];
    get_ans(1,1);
    ll ans = INF;
    for (int i = 1; i <= n; i ++) ans = min(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}

updated at 2022-02-02

Previous Post
图论之LCA
Next Post
背包DP