Submission #52108472

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

struct edge_s {
	int to, id, rev_id;
};

int ec[114514];
struct edge_s *es[114514];

void ae(int f, int t, int id, int rev_id) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]].to = t;
	es[f][ec[f]].id = id;
	es[f][ec[f]].rev_id = rev_id;
	ec[f]++;
}

int N;
int A[114514], B[114514];
int C[114514];

struct meow_s {
	uint64_t f_value;
	uint64_t sum_of_C;
};

struct meow_s memo[114514];
char memo_status[114514];
struct meow_s delta_cache[114514 * 2];
struct edge_s memo_tarinai[114514];

struct meow_s calc(int node, int from_edge_id) {
	struct meow_s ret = {0, 0};
	int i;
	if (memo_status[node] == 0) {
		/* メモが全く無い */
		for (i = 0; i < ec[node]; i++) {
			if (es[node][i].rev_id == from_edge_id) {
				memo_tarinai[node] = es[node][i];
			} else {
				struct meow_s delta = calc(es[node][i].to, es[node][i].id);
				/* 下層の分を足し、さらに上がったので C_i の合計を足す */
				ret.f_value += delta.f_value + delta.sum_of_C;
				/* 新しい C_i の合計を求める */
				ret.sum_of_C += delta.sum_of_C;
				/* キャッシュする */
				delta_cache[es[node][i].rev_id] = delta;
			}
		}
		ret.sum_of_C += C[node];
		memo[node] = ret;
		memo_status[node] = from_edge_id < 0 ? 2 : 1;
		return ret; /* 分岐で抜いているので、来た辺の分のロールバックは不要 */
	}
	if (memo_status[node] == 1) {
		/* 欠けている場所がある */
		if (memo_tarinai[node].rev_id == from_edge_id) {
			/* 同じ場所が欠けている */
			return memo[node];
		} else {
			/* 違う場所が欠ける → 埋めることができる */
			struct meow_s delta = calc(memo_tarinai[node].to, memo_tarinai[node].id);
			/* 下層の分を足し、さらに上がったので C_i の合計を足す */
			memo[node].f_value += delta.f_value + delta.sum_of_C;
			/* 新しい C_i の合計を求める */
			memo[node].sum_of_C += delta.sum_of_C;
			/* キャッシュする */
			delta_cache[memo_tarinai[node].rev_id] = delta;
			/* 欠けが解消したことを記録する */
			memo_status[node] = 2;
			/* 下のロールバックの処理に行く */
		}
	}
	ret = memo[node];
	if (from_edge_id >= 0) {
		/* 来た辺の分をロールバック */
		ret.f_value -= delta_cache[from_edge_id].f_value + delta_cache[from_edge_id].sum_of_C;
		ret.sum_of_C -= delta_cache[from_edge_id].sum_of_C;
	}
	return ret;
}

int main(void) {
	int i;
	uint64_t ans;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i < N; i++) {
		if (scanf("%d%d", &A[i], &B[i]) != 2) return 1;
		ae(A[i], B[i], 2 * (i - 1), 2 * (i - 1) + 1);
		ae(B[i], A[i], 2 * (i - 1) + 1, 2 * (i - 1));
	}
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &C[i]) != 1) return 1;
	}
	ans = calc(1, -1).f_value;
	for (i = 2; i <= N; i++) {
		uint64_t candidate = calc(i, -1).f_value;
		if (candidate < ans) ans = candidate;
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

/*

f(x) = (C_i × そこに行くまでのステップ数) の合計
これをサブツリーについて計算する
単純に C_i の和 → これを1段深くなるごとに加える

*/

Submission Info

Judge Result