[luoguP3047] [USACO12FEB]附近的牛Nearby Cows（DP）

传送门

dp[i][j][0] 表示点 i 在以 i 为根的子树中范围为 j 的解

dp[i][j][1] 表示点 i 在除去 以 i 为根的子树中范围为 j 的解

状态转移就很好写了

——代码

#include <cstdio> #include <cstring> #include <iostream> #define N 100001 int n, k, cnt; int f[N], dp[N][21][2], head[N], to[N << 1], next[N << 1], ans[N]; inline int read() inline void add(int x, int y) inline void dfs1(int u) } } inline void dfs2(int u, int k) } for(i = head[u]; i ^ 1; i = next[i]) } int main() for(i = 1; i <= n; i++) dp[i][0][0] = read(); dfs1(1); for(i = 1; i <= k; i++) dfs2(1, i); for(i = 1; i <= n; i++) ans[i] = dp[i][k][0] + dp[i][k 1][1]; for(i = 1; i <= n; i++) printf("%d\n", ans[i]); return 0; }

　　

上一篇：[luoguP3690] 【模板】Link Cut Tree

下一篇：[HDU3586]Information Disturbing（DP + 二分）

---

DP