动态规划课程树型dp例题

小G有一个大树

题目链接
求树的重心

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2000;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, siz[MAXN], root, temp = Inf;
void dfs(int x, int pre) {
    siz[x] = 1; int mx = 0;
    for(int i = head[x]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, x); siz[x] += siz[v];
        mx = max(mx, siz[v]);
    }
    mx = max(mx, n - siz[x]);
    if(mx < temp) {
        temp = mx;
        root = x;
    }
}
int main() {
    n = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, -1);
    printf("%d %d", root, temp);
    return 0;
}

Rinne Loves Edges

设 为以u为结点的子树，删最少多少边权可以使得所有叶子结点不到达根
对于一个节点的每一个分叉，一定会有一条边被转移，分出一个叉就代表一个至少一个子节点，那么对于每一颗子树，要么取其子树的结果，要么断掉和子树的边，取最小值转移即可
题目链接

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e5+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(){
    ll w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next;
    ll w;
}edge[MAXN<<1];
int cnt, head[MAXN], du[MAXN];
void add(int u, int v, ll w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    du[u]++;
}
void add_edge(int u, int v, ll w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, m, s;
ll dp[MAXN];
void dfs(int u, int pre) {
    if(du[u] == 1 && u != s) {
        dp[u] = Linf;
        return;
    }
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u);
        dp[u] += min(dp[v], edge[i].w);
    }
}
int main() {
    n = read(); m = read(); s = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    dfs(s, -1);
    printf("%lld", dp[s]);
    return 0;
}

Cell Phone Network

题目链接
每个点可以覆盖其相邻点，要求在树上选最少的点，使得整棵树被覆盖
考虑以 为根的子树， 被覆盖有三种情况

1. 本身就被选择
2. 的儿子被选择
3. 的父亲被选择

发现 的父亲对x也产生了影响，那么可以把父亲也设进x的状态，则dp的几个状态分别为

1. 自己被选择
2. 的儿子被选择
3. 的父亲被选择

那么考虑状态转移

1. 自己被选择时，其子节点选或者不选可以，且子节点不选的时候可以是其父节点 被选，那么转移方程则为
2. x的子树被选时，只需要其一个儿子被选就可以，那么对于其子树的两种选择1,2，先使 ,若 的儿子统计的状态中有1状态，即 的儿子本身被选择了，则 就可以算被覆盖，若 的所有儿子全部选择了2状态即 的所有儿子本身没有被选择，而是 的儿子 再下一层的儿子被选择了，间接的把 选择了，这种情况，需要在 的众多儿子中挑一个被选择，那么挑的这个儿子就是从被其儿子覆盖，变成其本身被选择，改变量最小的，统计一下就可以了
3. 的父亲被选择的时候，那么其儿子可以被选择也可以不被选择，转移则为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e4+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int dp[MAXN][12], n;
//0 i 自己
//1 i 儿子
//2 i 父亲
void dfs(int u, int pre) {
    dp[u][0] = 1; int pos = Inf;
    dp[u][13] = 0; dp[u][14] = 0;
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u); 
        dp[u][0] += min(dp[v][0], min(dp[v][15], dp[v][16]));
        dp[u][17] += min(dp[v][0], dp[v][18]);
        dp[u][19] += min(dp[v][0], dp[v][20]);
        pos = min(pos, dp[v][0] - min(dp[v][0], dp[v][21]));
    }
    dp[u][22] += pos;
}
int main() {
    n = read();
    memset(head, -1, sizeof head);
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, 0);
    printf("%d", min(dp[1][0], dp[1][23]));
    return 0;
}

二叉苹果树

题目链接
因为题目要求的是保留 条边最多的权值，那么就相当于选择 条边使得这些边的路径可以到根节点1，把边权下放到点权，则相当于选 个点，这些点连起来可以和根联通，这样的话若想选择点 ，则必须先选择的父节点,问题转换成了树形背包

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 500;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, q, val[MAXN], dp[MAXN][MAXN];

void dfs1(int u, int pre) {
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        val[v] = edge[i].w;
        dfs1(v, u); 
        for(int j = q+1; j >= 0; j--)
            for(int k = j; k >= 0; k--)
                if(j - k  >= 0)
                    dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
    }
    for(int i = q+1; i >= 1; i--)
        dp[u][i] = dp[u][i-1] + val[u];
}
int main() {
    n = read(); q = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    dfs1(1, -1);
    cout << dp[1][q+1];
    return 0;
}

没有上司的舞会

题目链接

设状态 为不选择 时权值最大最多是， 为选择 时权值最大为多少

1. 当选择 的时候，其儿子全部不能选择，那么转移方程则为
2. 当不选择 的时候，其儿子可以选择也可以不选择，那么转移方程为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2e4;
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, dp[MAXN][2], r[MAXN], du[MAXN], ans;
void dfs(int u) {
    dp[u][1] = r[u];
    int mx1 = 0, mx0 = 0;
    for(int i = head[u]; i != - 1; i = edge[i].next) {
        int v = edge[i].to;
        dfs(v);
        mx1 += dp[v][0];
        mx0 += max(dp[v][0], dp[v][1]);
    }
    dp[u][1] = r[u] + mx1;
    dp[u][0] = mx0;
    ans = max(ans, max(dp[u][1], dp[u][0]));
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> r[i];
    for(int i = 1; i < n; i++) {
        int l, k; cin >> l >> k;
        add(k, l); du[l]++;
    }
    int root;
    for(int i = 1; i <= n; i++) {
        if(du[i] == 0) root = i;
    }
    dfs(root);
    cout << ans;
    return 0;
}

Strategic game

题目链接

题目要求选择最少的点，覆盖所有的边，对于点 ,若选择 ,则其儿子结点可以选也可以不选，若不选 结点，则其儿子结点必须全部都选,转移方程为

1. 选 结点：
2. 不选 结点：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2000;
int n;
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
void init() {
    cnt = 0;
    memset(head, -1, sizeof head);
}
int vis[MAXN], dp[MAXN][2];
void dfs(int u, int pre) {
    vis[u] = 1; dp[u][1] = 1; dp[u][0] = 0;
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][1], dp[v][0]);
    }
}
void doit() {
    init();
    for(int i = 1; i <= n; i++) {
        char s[100]; scanf("%s", s);
        int x = 0, m = 0, top = 0;
        while(s[top] != ':') x = x*10 + s[top++]-'0';
        top += 2; while(s[top] != ')') m = m*10 + s[top++]-'0';
        for(int j = 1; j <= m; j++) {
            int v; scanf("%d", &v);
            add_edge(x, v);
        }
    }
    memset(dp, 0x3f, sizeof dp);
    memset(vis, 0, sizeof vis);
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(!vis[i]) dfs(i, -1), ans += min(dp[i][0], dp[i][1]);
    }
    cout << ans << endl;
}
int main() {
    while(scanf("%d", &n) != EOF) doit();
    return 0;
}

树上子链

题目链接

对于每个结点 来说，其最最长链肯定为它的最长子链和次长子链之和，统计一下就可以了，本题需要注意的是，因为点权可以为负数，那么有可能出现只选一个点的情况，答案记录的时候初始值要为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e5+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
struct Edge {
    int to, next, w;
}edge[MAXN<<1];
int cnt, head[MAXN];
void add(int u, int v, int w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void add_edge(int u, int v, int w = 0) {
    add(u, v, w); add(v, u, w);
}
int n, val[MAXN];
ll dp[MAXN], ans = -Linf;
void dfs(int u, int pre) {
    dp[u] = 0; ans = max(ans, 1ll* val[u]);
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u);
        ans = max(ans, dp[u] + dp[v] + 1ll*val[u]);
        dp[u] = max(dp[v], dp[u]);
    }
    dp[u] += val[u];
}
int main() {
    n = read();
    memset(head, -1, sizeof head);
    for(int i = 1; i <= n; i++) val[i] = read();
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs(1, -1);
    cout << ans;
    return 0;
}

吉吉王国

题目链接

没开 调了一个小时......

实际上就是 Rinne Loves Edges 这道题的一个变形，要求删去的最长长度最小，那么二分这个长度 ,设 为以 点为根的子树的最小花费，所以边长大于 的边全部不删，直接转移子树的答案，若边长小于等于 则这条边可以删也可以不删，比较下删这条边还是这个子树的代价，取更小的。

二分答案求解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e6+10;
char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(){
    ll w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = nc();
    if(ch == '-') w = -1, ch = nc();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
    return w * data;
}
ll n, m;
struct Edge {
    ll to, next, w;
}edge[MAXN<<1];
ll cnt, head[MAXN], du[MAXN];
void add(ll u, ll v, ll w = 0) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    du[u]++;
}
void add_edge(ll u, ll v, ll w = 0) {
    add(u, v, w); add(v, u, w);
}
ll dp[MAXN];
void dfs(ll u, ll pre, ll lim) {
    if(du[u] == 1 && u != 1) {
        dp[u] = Inf;
        return;
    }
    dp[u] = 0;
    for(ll i = head[u]; i != -1; i = edge[i].next) {
        ll v = edge[i].to;
        if(v == pre) continue;
        dfs(v, u, lim);
        if(edge[i].w > lim) dp[u] += dp[v];
        else dp[u] += min(dp[v], edge[i].w);
    }
}
bool check(ll lim) {
    dfs(1, -1, lim);
    return dp[1] <= m;
}
int main() {
    memset(head, -1, sizeof head);
    n = read(); m = read();
    for(ll i = 1; i < n; i++) {
        ll u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    ll l = 0, r = 2000, ans = -1;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}