Submission #52100242

---

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 * 3];
char memo_valid[114514 * 3];

struct meow_s calc(int node, int from_edge_id) {
	int memo_id = from_edge_id < 0 ? 2 * N + node : from_edge_id;
	struct meow_s ret = {0, 0};
	int i;
	if (memo_valid[memo_id]) return memo[memo_id];
	for (i = 0; i < ec[node]; i++) {
		if (es[node][i].rev_id != from_edge_id) {
			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;
		}
	}
	ret.sum_of_C += C[node];
	memo[memo_id] = ret;
	memo_valid[memo_id] = 1;
	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