相关链接
题目传送门:http://codeforces.com/contest/815/problem/C
解题报告
这题就是考察树DP优化复杂度的一种常用技巧
考虑暴力DP的话,复杂度是:$O(n^3)$的
但如果在父亲结点那里记录一个儿子节点的子树大小的前缀和,复杂度就变成了$O(n^2)$
证明也很简单,对于任意两个结点,只会在$LCA$处产生$1$的花费
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5009; const LL INF = 1e14; int n, head[N], nxt[N], to[N], sz[N]; LL b, f[N][N], g[N][N], c[N], d[N], t1[N], t2[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline void relax(LL &a, LL b) { a = a > b? b: a; } inline void DFS(int w) { f[w][0] = g[w][0] = 0; for (int i = head[w]; i; i = nxt[i]) { DFS(to[i]); memcpy(t1, f[w], sizeof(t1)); memcpy(t2, g[w], sizeof(t2)); for (int j = 0; j <= sz[w]; j++) { for (int k = 0; k <= sz[to[i]]; k++) { relax(f[w][j + k], t1[j] + f[to[i]][k]); relax(g[w][j + k], t2[j] + g[to[i]][k]); } } sz[w] += sz[to[i]]; } sz[w]++; for (int i = sz[w] - 1; ~i; i--) { g[w][i + 1] = g[w][i] + c[w] - d[w]; relax(f[w][i + 1], f[w][i] + c[w]); relax(g[w][i + 1], f[w][i + 1]); } g[w][0] = 0; } int main() { n = read(); b = read(); c[1] = read(); d[1] = read(); for (int i = 2; i <= n; i++) { c[i] = read(); d[i] = read(); AddEdge(read(), i); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { f[i][j] = g[i][j] = INF; } } DFS(1); for (int i = n; ~i; i--) { if (g[1][i] <= b) { printf("%d\n", i); exit(0); } } return 0; }