树形DP

CodeForces 855 C Helga Hufflepuff’s Cup

Posted on

前几天的上分场的树形DP

我敢说思路和我当时想得已经一模一样了,还有半个多小时的时候,gou bi 带鱼说把题目给他看一下,然后立马得出,树形DP解不了,肯定是树分治!
当时我在一个子问题上走不出来,于是就信了,然后开始划水……

md

题意:
给你一棵树,要你给树上的每一个节点赋值,赋值存在范围,再给你一个特殊值,除开特殊值意外的数值赋值次数不限,但是特殊值的相邻节点的值不能是特殊值,也不能是比特殊值大的值。
问方案数。

思路:
首先值得注意的是,特殊值赋值次数不超过10,这是一个重要突破口,这使得树形DP的解法存在可能性。
简单说就是在每个节点都保存当前节点为根节点的子树分别含有 [ 0, 10 ] 个特殊值的方案数。
但这还不好决策转移,我们还需要对当前值的范围作为状态进行判断。
我在比赛中只用了,当前值为特殊值,和不是特殊值两个状态,但是现在看了其他人的代码,发现三个状态更容易。
当前节点赋值小于特殊值,大于特殊值,等于特殊值。这样就很好转移,不细说,看代码都能秒懂。

我在比赛时候被卡的子问题是这样的,对于计算当前子树的特殊值数量为 n 的时候,我必须将当前根节点的每一个孩子的状态都理清楚。
比如说数量为 3 ,有三个孩子A,B,C
那么其方案数就是以下情况累加

  • \( A_0+B_0+C_3 \)
  • \( A_0+B_3+C_0 \)
  • \( A_3+B_0+C_0 \)
  • \( A_1+B_0+C_2 \)
  • \( A_0+B_1+C_2 \)
    ……
    ……

:wc 好多,复杂度好高,这不是组合问题么???
现在看来真是煞笔……

AC Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

int n, m, k, x;
vector<int> tree[maxn];

ll dp[maxn][3][11];
ll tmp[3][11];

void dfs(int u, int par)
{
    dp[u][0][0] = k - 1;
    dp[u][1][0] = m - k;
    dp[u][2][1] = 1;
    for (auto v : tree[u]) {
        if (v != par) {
            dfs(v, u);
            memset(tmp, 0, sizeof tmp);
            for (int i = 0; i <= x; i++)
                for (int j = 0; i + j <= x; j++) {
                    tmp[0][i + j] = (tmp[0][i + j] + dp[u][0][i] * (dp[v][0][j] + dp[v][1][j] + dp[v][2][j])) % mod;
                    tmp[1][i + j] = (tmp[1][i + j] + dp[u][1][i] * (dp[v][0][j] + dp[v][1][j])) % mod;
                    tmp[2][i + j] = (tmp[2][i + j] + dp[u][2][i] * dp[v][0][j]) % mod;
                }
            for (int i = 0; i <= x; i++)
                for (int j = 0; j < 3; j++)
                    dp[u][j][i] = tmp[j][i];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    scanf("%d%d", &k, &x);
    dfs(1, 0);
    int ans = 0;
    for (int i = 0; i <= x; i++)
        for (int j = 0; j < 3; j++)
            ans = (ans + dp[1][j][i]) % mod;
    printf("%d\n", ans);
    return 0;
}
树形DP

CodeForces 19E Fairy

Posted on

一道二分图性质的应用 + 树形DP ?

看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些

题意:
给你一个图,让你删除一条边,使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路:
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写,最后无奈去看题解了……

先整理一下判断思路:

  1. 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件
  2. 覆盖了所有的奇环,并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环,这个我还真没想到,但是在纸上画一画就是很显然的了,同时覆盖奇环和偶环的边删去后,两个环会变成一个新的环,偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现,随便生成一棵生成树,用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ,那么非树边必定不可能是满足条件的,因为非树边最多只能覆盖一个环,两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑,如果该非树边覆盖了奇环,则删之。
而对于树边,判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

void addEdge(int u, int v)
{
    edges[idx] = make_pair(v, head[u]);
    head[u] = idx++;
    edges[idx] = make_pair(u, head[v]);
    head[v] = idx++;
}

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}
树形DP

CodeForces 842 C Ilya And The Tree

Posted on

树上的选择性DP……
不是很懂其他人的做法,偶然间看到有人用ruby A了,我也就用ruby敲了一蛤
速度有点玄……

题意:
给你一棵树,每个节点都有权值,要你求每个节点到根节点所形成的树链 gcd。
其中每条树链都可以选择一个节点使得权值变为 0 。

思路:
感觉这就是裸题……
只不过就是把数组改成树上了而已。
用一个栈或者队列去遍历这棵树,对于每个节点是否变0都考虑一下就好了……

AC Code

#!/usr/bin/env ruby
# encoding: utf-8
n = gets.to_i
a = gets.split.map(&:to_i)
g = Array.new(n) {[]}

(n-1).times do
    u, v = gets.split.map(&:to_i)
    u, v = u-1, v-1
    g[u] << v
    g[v] << u
end

def GCD(a, b) return b == 0 ? a : GCD(b, a%b) end

dp = Array.new(n) { Array.new(2) { [] } }
dp[0] = [[a[0]], [0]]
par = [-1]*n

st = [0]
until st.empty?
    u = st.pop
    g[u].each do |v|
        next if v == par[u]
        par[v] = u
        st.push(v)
        dp[v][0] += dp[u][0].map{|x| GCD(x,a[v])}
        dp[v][1] += dp[u][0]
        dp[v][1] += dp[u][1].map{|x| GCD(x,a[v]) }
        2.times do |i|
            dp[v][i].uniq!
        end
    end
end

print a[0]
for u in 1...n do
    print " #{dp[u][1].max}"
end
树形DP

HDU4118 这也算树形DP?

Posted on

传送门

题意:

给你一个无向图,保证联通并且没有环(实质上就是一棵树……),要求:
每个点移动到另一个点去,并且不可能会有两个点移动到同一个点去,求最大移动距离和。

思路:

队友告诉我是图论……
…………
然后我特么还信了……
……………………

在看到结点个数达到 1e5 的时候我就应该意识到,基本不会是什么图论算法了。

我们可以这么想,先只考虑一半的节点移动到另一半的节点。
再是我们得确认一点,假如我可以得到这棵树的重心,那么重心一边的节点必然得移动到重心另一边的节点去才能使得移动距离和最大。(这个是显然的吧……举个例子 a-b-c-d a->c 必然会比 a->b 距离和大,而且,a->b影响的是 a,b 两个节点。)
然而我们无法轻松找到一棵树的重心,但是,我们从每一条边进行考虑,要使移动距离和最大,由该边断开形成的两棵子树,节点数目小的那一棵必然会全部移动到结点数目更多的那一棵,因为树的重心必然在节点数目更多的那一棵子树上,而且反过来移动也是不可能的吧…………

于是我们只要一次dfs就好了……

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n, idx;
int head[maxn];
int node_num[maxn];
long long ans;

struct node {
    int to;
    int dis;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].dis = w;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        node_num[i] = 0;
    }
    idx = 0;
    ans = 0;
}

int tree_dp(int cur, int pre)
{
    int total = 1, v, tmp;
    for (int it = head[cur]; ~it; it = edges[it].nxt) {
        v = edges[it].to;
        if (v != pre) {
            tmp = tree_dp(v, cur);
            ans += min(tmp, n - tmp) * edges[it].dis * 2; //因为来回,所以乘2
            total += tmp;
        }
    }
    return total;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T, u, v, w;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        cin >> n;
        init();
        for (int i = 1; i < n; i++) {
            cin >> u >> v >> w;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        tree_dp(1, -1);
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

很多题解都说是 树形DP ,为什么我指示觉得就是一个 DFS …… ~~虽然很有我之前学得模板风格~~

顺带一提的是,网上的题解质量真是越來越差了,很多核心部分的代码,直接一个显然得就没了……然后没多大卵用的东西瞎扯一堆……

树形DP

树形DP入门(持续更新中

Posted on
以前在暑假集训的时候搞得最多的还是图论相关,如果碰到树形结果很多时候就直接用搜……当然绝大多数时候也都T了……(当时也不喜欢分析复杂度,真是个坏习惯……
  

树形DP,简单说还是在树上做决策,只要把基础DP掌握好了我想应该不会是什么难事,只是换个场地罢了……

0. 入门题 POJ 2342

题意:
某公司要举办一次晚会,但是为了使得晚会的气氛更加活跃,每个参加晚会的人都不希望在晚会中见到他的直接上司,现在已知每个人的活跃指数和上司关系(当然不可能存在环),求邀请哪些人(多少人)来能使得晚会的总活跃指数最大。

思路:
定义数组dp[maxn][2],dp[k][0]表示第 k 人不去,dp[k][1] 表示第 k 人去。定义 son 为第 K 人的某个下属
我们从下往上分析,对于第 K 个人有以下去与不去两种情况

  • 假如 K 参加,那么对于他的每一个下属都不会去,那么就只能加上这个下属不去的这棵子树的值 dp[son][0]
  • 假如 K 不参加,那么他的下属可以选择去或者不去,当然我们要选择子树权值最大的 max(dp[son][0],dp[son][1])
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 10000;

vector<int> tree[maxn];
int n;
int dp[maxn][2];

void tree_dp(int cur, int pre)
{
    int sz = tree[cur].size();
    for (int i = 0; i < sz; i++) {
        int son = tree[cur][i];
        if (son != pre) {
            tree_dp(son, cur);
            dp[cur][1] += dp[son][0];
            dp[cur][0] += max(dp[son][0], dp[son][1]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u, v;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> dp[i][1];
            tree[i].clear();
            dp[i][0] = 0;
        }
        while (cin >> u >> v) {
            if (u == 0 && v == 0)
                break;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        tree_dp(1, -1);
        printf("%d\n", max(dp[1][0], dp[1][1]));
    }
    return 0;
}

顺便值得一提的是:
我看了很多网上的题解,无一都选择先找到树的根节点,然后从根节点进行向下dp。这样或许可以降低复杂度
~~因为出数据都习惯把初始树建的平衡一些……~~
但对于一棵树来说,无论你把哪一个节点定为根节点,它都能转化成另外一棵树,在这里是没有什么影响的。更何况,极端数据不排除会有极度不平衡的情况,其结果是一样的,该A的A,该WA的WA……还不如偷懒一点,提升一点码速。

1.1 向下递推 POJ 1947 Rebuilding Roads

题意:
给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为p个。

思路:
定义数组 dp[root][n] 表示以 当前节点为 root 节点,含有 n 个点所需删除的最小边数。
显然 dp[root][1]=root节点的所有孩子的个数+1(一个父亲节点),但是对于一棵树的根节点是没有父亲节点的。我这里先不考虑父亲节点,到最后再加上去。

初始状态已经确定,关键的还是 转移方程

dp[root][n] = min(dp[root][n],dp[root][n-k]+dp[root.son][k]-1);

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 160;
int n, p, ans;
vector<int> key[maxn];
int dp[maxn][maxn];

int tree_dp(int root)
{
    int total = 1, sz = key[root].size();
    for (int i = 0; i < sz; i++)
        total += tree_dp(key[root][i]);
    dp[root][1] = sz;
    for (int j = 0; j < sz; j++) {
        int son = key[root][j];
        for (int i = min(p, total); i > 1; i--) {
            for (int k = 1; k < i; k++) {
                dp[root][i] = min(dp[root][i], dp[root][i - k] + dp[son][k] - 1);
            }
        }
    }
    ans = min(ans, dp[root][p] + (root != 1));
    return total;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u, v;
    while (cin >> n >> p) {
        for (int i = 1; i <= n; i++)
            key[i].clear();
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i < n; i++) {
            cin >> u >> v;
            key[u].push_back(v);
        }
        ans = 0x3f3f3f3f;
        tree_dp(1);
        cout << ans << endl;
    }
    return 0;
}
1.2 树上的01背包 HDU 1561

题意:
给你一个森林,每个节点都赋予一个权值。让你取 m 个节点,使得节点和最大。
当然,取节点也是有条件的: 如果你要取走这个节点,那你必须先取走它的父亲节点。

思路:
额外增加一个超级根节点,让这片森林里的每棵树的根节点都成为这个超级根节点的孩子,以形成一棵树。
再与上题一样,在树上不断向下递推即可

转移方程: dp[root][i] = max( dp[root][i] , dp[root][i-k] + dp[root.son][k])

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long

using namespace std;

const int maxn = 205;
int n, idx, ans, m;
int head[maxn], dp[maxn][maxn], val[maxn];

struct edge {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        for (int j = 0; j <= n; j++)
            dp[i][j] = 0;
    }
    idx = val[0] = 0;
    m++;
}

void treeDP(int root)
{
    dp[root][1] = val[root];
    for (int it = head[root]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        treeDP(v);
        for (int i = m; i >= 1; i--)
            for (int k = 1; k < i; k++)
                dp[root][i] = max(dp[root][i], dp[root][i - k] + dp[v][k]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;
        init();
        for (int i = 1; i <= n; i++) {
            cin >> u >> val[i];
            addEdge(u, i);
        }
        treeDP(0);
        cout << dp[0][m] << endl;
    }
    return 0;
}
1.3 树上的最大连续序列 POJ 1192

题意:
题目虽然是中文,但说的非常繁琐。
简单概括就是 给定一个平面整点集,点与点间在|x1-x2| + |y1-y2| = 1 时两点连通,且形成的图没有回路~~其实就是一棵树啦~~,每个点有一个可正可负的权值,求最大权和连通子图。

思路:
和一维的 求连续最大权值序列 是一个思路

转移方程: dp = max(dp, dp + son )

//好激动呀,这是第一道我自己独立写出来的树形DP

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 1005;
int n, idx, ans;
int head[maxn];

struct node {
    int x, y, w;
} nodes[maxn];

struct edge {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

bool judgeAdj(int u, int v)
{
    return abs(nodes[u].x - nodes[v].x) + abs(nodes[u].y - nodes[v].y) == 1;
}

void init()
{
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    idx = ans = 0;
}

int treeDP(int cur, int pre)
{
    int dp = nodes[cur].w;
    for (int it = head[cur]; it != -1; it = edges[it].nxt)
        if (edges[it].to != pre) 
            dp = max(dp, dp + treeDP(edges[it].to, cur));
    return dp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n) {
        init();
        for (int i = 0; i < n; i++)
            cin >> nodes[i].x >> nodes[i].y >> nodes[i].w;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                if (judgeAdj(i, j)) {
                    addEdge(i, j);
                    addEdge(j, i);
                }
            }
        ans = treeDP(1, -1);
        cout << ans << endl;
    }
    return 0;
}