SDOI2017 苹果树
题意：
题目传送门
题解：
好神仙的题啊…… 考虑如果没有题目中的\(t - h \leq k\)的限制，那么这道题目就是树上依赖多重背包，复杂度为\(O(nk^2)\)，然后用单调队列优化就可以达到\(O(nk)\)，这个是比较好做的。然后我们考虑如何处理题目中给出的限制，实际上，题目中的限制可以转化成这样：假设取一个苹果的代价是\(1\)，那么我们可以花费\(0\)的代价取一条从根开始的链上的每个点各一个苹果，之后每取一个苹果都会产生\(1\)的代价，最终总代价不能超过\(k\)。 为什么这个转化是正确的呢？考虑我们取了一条链上每个点各一个苹果之后，最大深度\(h\)等于取的苹果个数\(t\)，所以这部分相当与是没有代价的。然后我们考虑枚举这条链之后，整棵树变成了什么样。大致分成四个部分：
在链上并且是免费取的部分在链上并且但是需要付出代价的部分在链的左边的部分在链的右边的部分
然后我们发现这棵树除了链之外被分成了两个部分，而在链右边的部分实际上是比较容易计算的，因为容易发现这部分在\(dfn\)序上是连续的一段，我们可以直接处理出来。至于左边的部分，由于他们\(dfn\)序不是连续的，我们似乎无从下手。但是反过来考虑，我们将边表\(reverse\)一下，那么再次求一边\(dfn\)序之后，链的左右两半部分会交换过来，那么原本的左半部分的\(dp\)值就变得好求了。这样我们记\(dp[i][j]\)表示\(dfn\)序在\([dfn[i] + 1,n]\)这个区间内，取\(k\)个苹果的最大价值，这个就可以在\(O(nk)\)的时间处理出来。然后我们考虑如何处理在链上并且需要付出代价部分的值，一种方法就是我们可以再次对链上进行一次多重背包，但是有一种更加简单的做法。我们将树上的节点都拆成两个节点，一个节点苹果个数为\(1\)，连原图中的边，另一个节点苹果个数为\(a_i - 1\)，只向这个点原来的节点连边。容易证明这样的转化也是正确的而拆了点之后，链上的点的贡献也被算到3.4两个部分中去了，就不用单独计算了。枚举选择的链，以及链右边选了几个苹果，最后答案就是这四个部分的权值之和。不过这题的时间空间都似乎挺卡的，我似乎开了\(O2\)才卡着过去的……
Code
#pragma GCC optimize(2,"inline","Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 50;
const int M = 5e5 + 50;
int Q, n, clck, k;
int dfn[N], a[N], v[N], sz[N], id[N], Mv[N];
vector<int> f[N], t[N];
vector<int> G[N];
void read(int &x) {
x = 0; int f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '=') f = -1; ch = getchar();}
while(ch >='0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f;
}
void clear(vector<int> &x) { vector<int> tmp; swap(tmp, x);}
void Init() {
for(int i = 0; i <= n * 2; i++) {
clear(G[i]); clear(f[i]); clear(t[i]);
}
}
void Dfs(int o, int V, int tp) {
sz[o] = 1; V += v[o]; Mv[o] = V;
for(int i = 0; i < (int)G[o].size(); i++) {
int to = G[o][i];
Dfs(to, V, tp);
sz[o] += sz[to];
}
if(tp == 0) dfn[id[o] = ++clck] = o;
else dfn[++clck] = o;
}
void Dp(int x, int y) {
static int que[M];
int l = 1, r = 0;
que[++r] = 0;
for(int i = 1; i <= k; i++) {
while(l <= r && i - que[l] > a[dfn[y]]) ++l;
if(l <= r) t[y][i] = t[x][que[l]] + v[dfn[y]] * (i - que[l]);
else t[y][i] = 0;
while(l <= r && t[x][i] >= t[x][que[r]] + (i - que[r]) * v[dfn[y]]) --r;
que[++r] = i;
}
}
int main() {
read(Q);
while(Q--) {
Init();
read(n); read(k);
for(int i = 1, x; i <= n; i++) {
read(x); read(a[i]); read(v[i]);
if(x) G[x].push_back(i);
}
for(int i = 1; i <= n; i++) {
v[i + n] = v[i];
a[i + n] = a[i] - 1;
a[i] = 1;
G[i].push_back(i + n);
}
clck = 0;
Dfs(1, 0, 0);
for(int i = 0; i <= n * 2; i++) f[i].resize(k + 5), t[i].resize(k + 5);
for(int i = 1; i <= n * 2; i++) {
Dp(i - 1, i);
for(int j = 0; j <= k; j++) {
t[i][j] = max(t[i][j], t[i - sz[dfn[i]]][j]);
if(j) t[i][j] = max(t[i][j], t[i][j - 1]);
}
}
swap(f, t);
for(int i = 1; i <= n * 2; i++) reverse(G[i].begin(), G[i].end());
clck = 0;
Dfs(1, 0, 1);
for(int i = 1; i <= n * 2; i++) {
Dp(i - 1, i);
for(int j = 0; j <= k; j++) {
t[i][j] = max(t[i][j], t[i - sz[dfn[i]]][j]);
if(j) t[i][j] = max(t[i][j], t[i][j - 1]);
}
}
int ans = 0;
for(int i = 1; i <= n * 2; i++) {
if(dfn[i] > n) continue;
int pos = id[dfn[i]] - sz[dfn[i]];
for(int j = 0; j <= k; j++) {
ans = max(ans, Mv[dfn[i]] + t[i - 1][j] + f[pos][k - j]);
}
}
printf("%d\n", ans);
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10532085.html
