紫书 习题 11-16 UVa 1669（树形dp）

想了很久， 以为是网络流最大流， 后来建模建不出来， 无奈。

后来看了 https://blog.csdn.net/hao_zong_yin/article/details/79441180

感觉思路很巧妙。

首先题目等价于让每条边经过的次数最多。

那么假设一条边点a到点b， 假设以b为根节点的子树中的节点数为pb， 那么剩下的

以以b为根节点的子树中的节点数为pa

我们假设pa > pb

那么从a这边去b这边， 最多只能走pb次， 因为不能到同一个点，b那边最多就pb个点

如果经过次数大于pb的话就说明肯定b那边的点至少一个点经过了两次以上

那么b这边最多去a那边也是pb次， 这次是因为起点就这么多个点。

所以这条边走过的次数就是pb * 2， 算上权值就是pb * 2 * cost

那么我们就可以得出， 对于一条边u1, u2， 那么经过这条边的最大权值为

min（dp[u1], n - dp[u1]） * cost * 2

dp[u]表示以u为根节点的子树中节点的个数。

所以我们每条边都加上最大权值即为答案

最后注意要开 long long。

#include<cstdio>

#include<algorithm>

#include<vector>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 112345;

struct node { int v, w; };

vector<node> g[MAXN];

int n, dp[MAXN];

ll ans;

void dfs(int u, int fa)

{

	dp[u] = 1;

	REP(i, 0, g[u].size())

	{

		int v = g[u][i].v, w = g[u][i].w;

		if(v == fa) continue;

		dfs(v, u);

		ans += min(dp[v], n - dp[v]) * w * 2;

		dp[u] += dp[v];

	}

}

int main()

{

	int T, kase = 0;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d", &n);

		REP(i, 0, n) g[i].clear();

		REP(i, 0, n - 1)

		{

			int u, v, w;

			scanf("%d%d%d", &u, &v, &w);

			u--; v--;

			g[u].push_back(node{v, w});

			g[v].push_back(node{u, w});

		}

		ans = 0;

		dfs(0, -1);

		printf("Case #%d: %lld\n", ++kase, ans);

	}

	return 0;

}