题目链接：点击打开链接
题意：
给定n个点的有向树
下面n-1行给出正向的边。
问：
修改尽可能小的边的方向，可以任选2个起点使得这两个点bfs能遍历完所有点。
思路：
枚举一条边，把树分成两部分，每次计算这两部分的最小花费。
那么这样就变成一个子树上的dp。
对于一棵树所需要修改的最小边方向的方法：
首先容易求出：dp[i]表示以i为根的子树，用i作为起点的花费.
此时若以root为起点则代价就是cost[root] = dp[root], 若以树中任意一点u为起点
则代价就是cost[u] = dp[root] + (root->u方向的边数) – (u->root方向的边数)
那么为了得到最小的cost[i], 则就要使得(root->u方向的边数) – (u->root方向的边数)最大。
所以维护(root->u方向的边数) – (u->root方向的边数) 的最大值，最小的cost[i] = dp[root] – max;
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;const int N = 1e5 + 10;struct Edge{int from, to, dis, nex;}edge[N<<1];int head[N], edgenum;void add(int u, int v, int d){Edge E = { u, v, d, head[u] };edge[edgenum] = E;head[u] = edgenum++;}int dp[N];int n, mx;void dfs(int u, int fa, int val){dp[u] = 0;for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to;if (v == fa)continue;dfs(v, u, val – edge[i].dis);dp[u] += dp[v] + (edge[i].dis!=1);}mx = max(mx, val);}int main(){while (cin >> n){if (n == 1){ puts("0"); continue; }memset(head, -1, sizeof head);edgenum = 0;for (int i = 1, u, v; i < n; i++){scanf("%d %d", &u, &v);add(u, v, 1);add(v, u, -1);}int ans = 1 << 30;for (int i = 0, u, v; i < edgenum; i += 2){u = edge[i].from; v = edge[i].to;mx = -(1<<30);dfs(u, v, 0);int tmp = dp[u] – mx;mx = -(1<<30);dfs(v, u, 0);tmp += dp[v] – mx;ans = min(ans, tmp);}printf("%d\n", ans);}return 0;}
，谁是谁生命的点缀。
