uva 12223 - Moving to Nuremberg(树形dp）

题目链接：uva 12223 - Moving to Nuremberg

题目大意：给出n，表示有n个位置，n个位置有n-1条边，形成一个无根的树，每条边上都有权值。现在每个位置都有一个景点，一个人想在一年之内去ki次景点，所以接下来给出m，表示说在m个位置上有这个人想去的地方，给出位置以及想去的次数（注意，每去一个景点都要返回自己的住处），然后问说，这个人该住在哪里走的路程才最短。

解题思路：因为给出的是一个无根树，没有根的话就不好有个基准，所以我们在这里默认把节点1做为根，这样的话就变成了有根的树了。那么假设现在u为当前处理的节点，它又一个子节点v，那么u-v这条要走的次数即为以v为根的子树上所有节点要访问的次数之和乘以2（注意来回），那么这个值可以用cnt[v]处理出来，所以第一次的dfsCnt即将以1为根节点的树的所有cnt处理出来，并计算出dp[1]（以1为根需要的路程）作为基准，然后假如u-v相连，且dp[u]已经知道了，那么dp[v]和dp[u]相差的部分起始只有u-v这条边走的次数而已。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
const int N = 50005;

struct state {
	int v;
	ll w;
	state (int v = 0, ll w = 0) {
		this->v = v;
		this->w = w;
	}
};

int n, vis[N];
ll ans, sum, cnt[N], dp[N];
vector<state> g[N];

void init () {
	int a, b;
	ll w;

	scanf("%d", &n);

	sum = 0;
	memset(dp, 0, sizeof(dp));
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i <= n; i++) 
		g[i].clear();

	for (int i = 1; i < n; i++) {
		scanf("%d%d%lld", &a, &b, &w);
		g[a].push_back(state(b, w));
		g[b].push_back(state(a, w));
	}

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%lld", &a, &w);
		sum += w;
		cnt[a] = w;
	}
}

void dfsCnt (int u, ll W) {
	vis[u] = 1;
	dp[1] += W * cnt[u];
	for (int i = 0; i < g[u].size(); i++) {
		state cur = g[u][i];

		if (vis[cur.v]) continue;

		dfsCnt(cur.v, cur.w*2 + W);

		cnt[u] += cnt[cur.v];
	}
}

void dfsAns (int u) {
	vis[u] = 1;
	ans = min (ans, dp[u]);

	for (int i = 0; i < g[u].size(); i++) {
		state cur = g[u][i];
		if (vis[cur.v]) continue;

		dp[cur.v] = dp[u] + (sum - 2*cnt[cur.v]) * cur.w*2;
		dfsAns(cur.v);
	}
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();

		memset(vis, 0, sizeof(vis));
		dfsCnt(1, 0);

		ans = dp[1];
		memset(vis, 0, sizeof(vis));
		dfsAns(1);

		bool flag = false;
		printf("%lld\n", ans);
		for (int i = 1; i <= n; i++) if (ans == dp[i]) {
			if (flag) printf(" ");
			printf("%d", i);
			flag = true;
		}
		printf("\n");
	}
	return 0;
}