結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define int long long
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N = 2e5+5;
int rt[N],sz[N],b[N];
struct lft{
	#define ls node[u].lc
	#define rs node[u].rc
	struct aa{
		int lc,rc,vl;
	}node[N*2];
	int dis[N],ct;
	void pushup(int u){
		dis[u] = dis[rs]+1;
	}
	int merge(int u,int v){
		if(!u||!v){
			return u+v;
		}
		if(node[u].vl<node[v].vl){
			swap(u,v);
		}
		rs = merge(rs,v);
		if(dis[ls]<dis[rs]){
			swap(ls,rs);
		}
		pushup(u);
		return u;
	}
	int pop(int u){
		sz[u]--;
		int v = node[rt[u]].vl;
		rt[u] = merge(node[rt[u]].lc,node[rt[u]].rc);
		return v;
	}
	void ins(int u,int x){
		node[++ct] = (aa){0,0,x};
		rt[u] = merge(rt[u],ct);
		sz[u]++;
	}
}T;
int id,n,a[N];
vector<int>E[N];
void dfs(int u,int f){
	for(int x:E[u]){
		if(x==f){
			continue;
		}
		dfs(x,u);
		rt[u] = T.merge(rt[u],rt[x]);
		b[u]+=b[x];sz[u]+=sz[x];
	}
	while(1){
//		cout<<"RT:"<<u<<" "<<T.node[rt[u]].vl<<" "<<sz[u]<<"\n";
		if(a[u]>T.node[rt[u]].vl||sz[u]==0){
			T.ins(u,a[u]);
			break;
		}
		if(sz[u]==1){
//			int z = T.pop(u);
			b[u]+=a[u]-T.pop(u);
			break;
		}
		a[u]-=T.pop(u);a[u]+=T.pop(u);
	}
//	cout<<"U:"<<u<<" "<<rt[u]<<" "<<T.node[rt[u]].vl<<" "<<b[u]<<" "<<sz[u]<<"\n"; 
}
signed main(){
//	id = read();
	n = read();
	for(int i=1;i<=n;i++){
		a[i] = read();
	}
	T.node[0].vl = 0;
	for(int i=1;i<n;i++){
		int u,v;
		u = read();v = read();
		E[u].push_back(v);E[v].push_back(u);
	}
	dfs(1,0);
	int ans = 0;int t = 1;
	while(sz[1]){
		ans+=t*T.pop(1);
		t = -t;
//		cout<<"ANS:"<<ans<<"\n";
	}
//	cout<<"B:"<<b[1]<<"\n";
	ans+=t*b[1];
	cout<<ans<<"\n";
	return 0;
}
/*
????? <=2 ???????????????

?????? <=3?????????? 2 ????????????

????????????????????????????????????????????

???????????????? au-av ???????

????????????????????????????????????????? a ????? b

???? a ??????????b ???????????? b ???

?? <=3 ????????????? 2 ???????????

??????????????????????? 2 ?????????????? 2 ????? a ?????

??????????????????????????????????????????????? 

?????????????????????????????????????????????????? 

??????????????????? 

???? 1 ???????? b ?????? 0 ??????????? xu ??

??????????????????????????????????????? a ?????b ?? 

??????????????????????????? 
*/
0