結果

問題 No.1154 シュークリームゲーム（Hard）
ユーザー Guo yinhe
提出日時 2025-07-28 10:47:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,976 bytes
コンパイル時間 2,113 ms
コンパイル使用メモリ 201,608 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-28 10:47:15
合計ジャッジ時間 4,099 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Date: 2025-07-28 09:30:47
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P emplace_back
#define CLEAR(a, v) memset(a, (v), sizeof(a))
#define pii pair<int, int>
#define fi first
#define se second
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
//char buf[1 << 20], *p1, *p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
inline int rd() {
    int s = 0, m = 0; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') m = 1; ch = getchar();}
    while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
    return m ? -s : s;
}
bool MBE;
namespace SOLVER {
const int N = 1005;
int n, x[N], b[N]; vector<int> g[N], a[N];
void dfs(int u, int p) {
    for(int v : g[u]) if(v != p) {dfs(v, u), b[u] += b[v]; for(int x : a[v]) a[u].P(x);}
    sort(a[u].begin(), a[u].end()); int now = x[u], sz = a[u].size();
    for(int i = sz - 1; i >= 0; i -= 2) {
        if(now > a[u][i]) {a[u].P(now), now = 1e18; break;} if(!i) continue;
        now = now - a[u][i] + a[u][i - 1], a[u].pop_back(), a[u].pop_back();
    }
    if(now != 1e18) {
        if(sz % 2) b[u] += now - a[u][0], a[u].pop_back(), assert(a[u].size() == 0); 
        else a[u].P(now);
    }
    // cerr << b[u] << ' '; for(int x : a[u]) cerr << x << ' '; cerr << endl;
}
void MAIN() {
    n = rd(); rep(i, 1, n) x[i] = rd(); 
    rep(i, 2, n) {int u = rd(), v = rd(); g[u].P(v), g[v].P(u);}
    dfs(1, 0); reverse(a[1].begin(), a[1].end()), a[1].P(b[1]);
    int ans = 0, fl = 1; for(int x : a[1]) ans += fl * x, fl *= -1;
    cout << ans << endl;
}
}
bool MED;
signed main() {
    // freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    // cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    for(int tt = 1; tt; tt--) SOLVER::MAIN();
    cerr << (&MBE - &MED) / 1024 << " KB, " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}
0