ZOJ - 3949 Edge to the Root——树形dp

ZOJ - 3949 Edge to the Root——树形dp

首先用dp1【i】维护一下【以节点i为根节点的子树】的节点数（包括i）

然后从根节点向下递推，用dp2【i】表示在根节点和i节点之间连边以后的距离之和，那么我们从节点u推到他的子节点v时，距离之和首先要在dp2【u】的基础上减去dp1【v】，然后要计算v节点到根节点这条链上一半节点的距离变化，举个例子，假设1为根节点，4为v节点，链为1->2->3->4，那么之前说的一半节点就是指3和4两个节点，如果链为1->2->3->4->5，那么之前说的一半节点就是4和5两个节点，一半节点本质上就是将连线从u改到v后距离增大的那些节点，最后将一半节点的距离变化加到之前的结果上就是当前的结果了

然后注意一下边界以及向下取整之类的问题

#include #include #include #include #include using namespace std;const int maxn = 2e5 + 10;const long long INF = 1e12;int T, n;vector G[maxn];long long sum, dp1[maxn], dp2[maxn], dep[maxn];void dfs1(int u, int f, int d) { sum += d - 1; dp1[u] = 1; for (int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if (v == f) continue; dfs1(v, u, d+1); dp1[u] += dp1[v]; }}void dfs2(int u, int f, int d) { for (int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if (v == f) continue; dep[d+1] = v; dp2[v] = dp2[u] + dp1[dep[(d+2)/2+1]] - 2*dp1[v]; dfs2(v, u, d+1); }}int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) G[i].clear(); int u, v; for (int i = 1; i < n; i++) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } sum = 0; dfs1(1, 0, 1); dp2[1] = sum; dep[1] = 1; for (int i = 0; i < (int)G[1].size(); i++) { int v = G[1][i]; dp2[v] = sum; dep[2] = v; dfs2(v, 1, 2); } long long ans = INF; for (int i = 1; i <= n; i++) ans = min(ans, dp2[i]); printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。