传送门
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; }
上一篇：[luoguP3565] [POI2014]HOT-Hotels（dfs）
下一篇：[POJ3162]Walking Race（DP + 单调队列）
DP
