【题解】CF238C：World Eater Brothers

原题传送门 大意是改变最少的边的方向使得选两个点，能遍历完整棵树 考虑枚举两个起点。 对于一个起点，用树形dp计算出$d{p}_u$表示以$u$为根的子树的答案 然后若以$u$作为真正的起点，那么答案就是$d{p}_u$ 如果选择$u$子树中的某个点$v$作为起点，那么答案是 $d{p}_u-(u->v反向的边)+(u->v正向的边)$ 发现所以维护$-(u->v反向的边)+(u->v正向的边)$的最小值，加上$d{p}_u$就是答案

Code：

#include <bits/stdc++.h> #define maxn 3010 using namespace std; struct Edge{ int to, next, len; }edge[maxn << 1]; int num, head[maxn], dp[maxn], Min, n; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; } void dfs(int u, int pre, int val){ dp[u] = 0; for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to, l = edge[i].len; if (v != pre){ dfs(v, u, val + l); dp[u] += dp[v] + (l != 1); } } Min = min(Min, val); } int main(){ n = read(); if (n == 1) return puts("0"), 0; for (int i = 1; i < n; ++i){ int x = read(), y = read(); addedge(x, y, 1), addedge(y, x, -1); } int ans = 1e9; for (int u = 1; u <= n; ++u) for (int i = head[u]; i; i = edge[i].next) if (edge[i].len == 1){ int v = edge[i].to, tmp; Min = 1e9; dfs(u, v, 0); tmp = dp[u] + Min; Min = 1e9; dfs(v, u, 0); tmp += dp[v] + Min; ans = min(ans, tmp); } printf("%d\n", ans); return 0; }