JZOJ 5344【NOIP2017模拟9.3A组】摘果子

罕见的树形背包啊 好东西要做做 (不过总感觉不会考) 先放题目

Description

Input

上面由字改成有 强迫症=-=

Output

Sample Input

7 9
39 6
13 2
22 6
7 4
-19 5
28 6
-17 1
2 1
3 2
4 1
5 4
6 2
7 3

Sample Output

52

Data Constraint

树形背包哇 好东西哇 我不会哇

背包放树上好处都有啥 谁说对了送给他 废话 挂那么高 当然是拿不到包了啦

好了好了不乱搞了开始讲题目

先讲讲树形背包常用套路

一个貌似是右儿子变兄弟？不行这个我做不来 概念上和伦理上都无法接受

好了我讲第二个dfs序的做法 超像树剖的！

树剖大法好啊 这里引用点树剖的概念 id 和 oid

由于本题每个点的状态不止会被他儿子们影响 所以本题我是先dfs预处理后再全部处理的 不过边搜边弄貌似也可以？

首先我们肯定要找个根啦 还好本题说了 1 号节点是根 不然这种题目随便确定根是不行的 要用出度判断

然后我们可以考虑两种情况

        选：那么我们就可以更新子节点

        不选：那我们就跳过该点的所有子节点

普通树形dp的话直接更新判重就好了 但是树形背包到时候要预处理惹 而且预处理得从底开始 (因为之前的不选要跳到后面来 后面不选的前面 v 满了的时候会跳过没关系) 所以 id 和 oid 数组走起 当然其实这里用不到 id 数组 (我等会放两个代码)

那么要跳过的话就得把每个点的siz预处理出来 但 id + siz + 1 这种东西太麻烦了 干脆 siz 直接连子树末点 id + 1

好了好了动态规划方程我可以摆出来了

        选：dp[x][v] = max(dp[x][v],dp[x + 1][v - dusu[oid[x]] + value[oid[x]]) //这里 x + 1 是选了子节点的 如果选另外的子节点就是下面的跳 或者跳了再跳 以此类推

        不选：dp[x][v] = max(dp[x][v],dp[siz[oid[x]]][v]) //就是用 siz 跳啦

最后我们找 dp[1][0~v] 就可以了 因为不一定到上界价值才最大

好了下放代码

//id去掉的 用siz判有无经过该点
#include <cstdio>
const int MAXN = 2005;
struct edge {int next,to;
} e[MAXN << 1];
struct fruit {int v,w;
} s[MAXN];
int first[MAXN],dp[MAXN][MAXN],oid[MAXN],siz[MAXN],tot;
inline int max(int x,int y) {return x > y ? x : y;}
inline int r()
{char q = getchar();int x = 0,y = 0;while (q < '0' && q != '-' || q > '9') q = getchar();if (q == '-') q = getchar(),++ y;while ('0' <= q && q <= '9')x = (x << 3) + (x << 1) + q - (3 << 4),q = getchar();return y ? -x : x;
}
inline void add(int x,int y)
{e[++tot].next = first[x];e[tot].to = y;first[x] = tot;
}
inline void dfs(int p)
{++siz[p];oid[++tot] = p;for (int a = first[p],b = e[a].to ; a ; a = e[a].next,b = e[a].to)if (!siz[b]) dfs(b);siz[p] += tot;
}
int main()
{int n = r(),m = r(),x,y;for (int a = 1 ; a <= n ; ++ a)s[a].w = r(),s[a].v = r();for (int a = 1 ; a <  n ; ++ a)x = r(),y = r(),add(x,y),add(y,x);tot = 0;dfs(1);tot = 0;for (int a = n ; a >= 1 ; -- a)for (int b = 0 ; b <= m ; ++ b){if (b >= s[oid[a]].v)dp[a][b] = max(dp[a][b],dp[a + 1][b - s[oid[a]].v] + s[oid[a]].w);dp[a][b] = max(dp[a][b],dp[siz[oid[a]]][b]);}for (int a = 0 ; a <= m ; ++ a) tot = max(tot,dp[1][a]);printf("%d\n",tot);return 0;
}//用id判断有无经过该点 id在树剖中通常搭配线段树查询节点用 常打是个好习惯
#include <cstdio>
const int MAXN = 2005;
struct edge {int next,to;
} e[MAXN << 1];
struct fruit {int v,w;
} s[MAXN];
int first[MAXN],dp[MAXN][MAXN],id[MAXN],oid[MAXN],siz[MAXN],tot;
inline int max(int x,int y) {return x > y ? x : y;}
inline int r()
{char q = getchar();int x = 0,y = 0;while (q < '0' && q != '-' || q > '9') q = getchar();if (q == '-') q = getchar(),++ y;while ('0' <= q && q <= '9')x = (x << 3) + (x << 1) + q - (3 << 4),q = getchar();return y ? -x : x;
}
inline void add(int x,int y)
{e[++tot].next = first[x];e[tot].to = y;first[x] = tot;
}
inline void dfs(int p)
{id[p] = ++tot;oid[tot] = p;for (int a = first[p],b = e[a].to ; a ; a = e[a].next,b = e[a].to)if (!id[b]) dfs(b);siz[p] = tot + 1;
}
int main()
{int n = r(),m = r(),x,y;for (int a = 1 ; a <= n ; ++ a)s[a].w = r(),s[a].v = r();for (int a = 1 ; a <  n ; ++ a)x = r(),y = r(),add(x,y),add(y,x);tot = 0;dfs(1);tot = 0;for (int a = n ; a >= 1 ; -- a)for (int b = 0 ; b <= m ; ++ b){if (b >= s[oid[a]].v)dp[a][b] = max(dp[a][b],dp[a + 1][b - s[oid[a]].v] + s[oid[a]].w);dp[a][b] = max(dp[a][b],dp[siz[oid[a]]][b]);}for (int a = 0 ; a <= m ; ++ a) tot = max(tot,dp[1][a]);printf("%d\n",tot);return 0;
}