結果

問題 No.1154 シュークリームゲーム（Hard）
コンテスト
ユーザー vjudge1
提出日時 2026-01-08 16:06:14
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,375 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,090 ms
コンパイル使用メモリ 215,292 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-08 16:06:18
合計ジャッジ時間 3,769 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector < int >;
using pii = pair < int, int >;
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(), (a).end()
#define qio() cin.tie(0) -> sync_with_stdio(0)
#define L(i, j, k) for (int i = j; i <= int(k); i++)
#define R(i, j, k) for (int i = j; i >= int(k); i--)

const int N = 1003;

int n, tot, sz[N], rt[N], ls[N], rs[N];
ll ans, a[N], val[N], End[N];
vi G[N];

int merge(int x, int y) {
	if (!x | !y) return x | y;
	if (val[x] < val[y]) swap(x, y);
	rs[x] = merge(rs[x], y);
	return swap(ls[x], rs[x]), x;
}
ll pop(int x) {
	ll ret = val[rt[x]];
	return sz[x]--, rt[x] = merge(ls[rt[x]], rs[rt[x]]), ret;
}

void dfs(int u, int f) {
	for (int v : G[u]) if (v != f) {
		dfs(v, u);
		End[u] += End[v];
		sz[u] += sz[v];
		rt[u] = merge(rt[u], rt[v]);
	}
	for (; sz[u] >= 0; a[u] -= pop(u), a[u] += pop(u)) {
		if (sz[u] == 0 || a[u] >= val[rt[u]]) {
			val[++tot] = a[u];
			sz[u]++;
			rt[u] = merge(rt[u], tot);
			return;
		} else if (sz[u] == 1) {
			End[u] += a[u] - pop(u);
			return;
		}
	}
}

int main() {
	qio(), cin >> n;
	L(i, 1, n) cin >> a[i];
	L(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1, 0);
	int sgn = 1;
	for (; sz[1]; sgn *= -1) ans += pop(1) * sgn;
	ans += sgn * End[1];
	cout << ans << '\n';
	return 0;
}
0