結果

問題 No.1154 シュークリームゲーム（Hard）
コンテスト
ユーザー wjwweiwei
提出日時 2026-01-08 14:26:42
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,587 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,086 ms
コンパイル使用メモリ 344,628 KB
実行使用メモリ 276,776 KB
最終ジャッジ日時 2026-01-08 14:26:52
合計ジャッジ時間 8,368 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 11 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
int sub,n;
ll a[N];
vector<int>e[N];
priority_queue<ll>pq[N];
int rt[N],cnt;
int merge(int u,int v){
	if(pq[u].size()<pq[v].size())swap(u,v);
	while(!pq[v].empty())pq[u].push(pq[v].top()),pq[v].pop();
	return u;
}
ll rub[N];
int pf[N];
void dfs(int u,int fa){
	if(fa)e[u].erase(find(e[u].begin(),e[u].end(),fa));
	pf[u]=fa;	
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
}
bool era[N];
void solve(int u){
	rt[u]=++cnt;
	if(e[u].empty()){
		pq[rt[pf[u]]].push(a[u]);
		return ;
	}
	for(auto v:e[u]){
		solve(v);
	}
	if(u==1)return ;
	while(!pq[rt[u]].empty()){
		int op=-1;
		ll cur=0;
		while(!pq[rt[u]].empty()){
			ll v=pq[rt[u]].top();
			if(v>=a[u])cur+=op*v,pq[rt[u]].pop();
			else break; 
			op=-op;
		}
		a[u]+=cur;
		if(pq[rt[u]].empty()){
			if(op==1)era[u]=1;
			break;
		}
		if(op==1){
			a[u]+=pq[rt[u]].top();
			pq[rt[u]].pop();
		}
		else{
			if(pq[rt[u]].top()<a[u])break;
		}
	}
	if(era[u])rub[u]+=a[u];
	else{
		pq[rt[pf[u]]].push(a[u]);
		rt[pf[u]]=merge(rt[pf[u]],rt[u]);
	}
	rub[pf[u]]+=rub[u];
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>sub>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(1,0);
	solve(1);
	int op=-1;
	ll ans=a[1];
	vector<ll>now;
	while(!pq[rt[1]].empty())now.push_back(pq[rt[1]].top()),pq[rt[1]].pop();
	for(auto v:now){
		ans+=op*v;
		op=-op;
	}
	if(op==1)ans+=rub[1];
	else ans-=rub[1];
	cout<<ans<<"\n";
	return 0;
}
//T3 < T1,T2 这一块
0