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;
}