結果

問題 No.2654 [Cherry 6th Tune] Re: start! (Black Sheep)
ユーザー kotatsugamekotatsugame
提出日時 2024-02-23 22:46:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 538 ms / 7,000 ms
コード長 2,233 bytes
コンパイル時間 965 ms
コンパイル使用メモリ 89,920 KB
実行使用メモリ 68,224 KB
最終ジャッジ日時 2024-09-29 07:54:14
合計ジャッジ時間 11,849 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cassert>
using namespace std;
int N;
int A[2<<17];
vector<int>G[2<<17];
multiset<int>L,R;
long long Lsum=0,Rsum=0;
long long ans[2<<17];
map<int,int>cnt;
void dfs(int u,int p)
{
	cnt[A[u]]++;
	if(L.size()==R.size())
	{
		R.insert(A[u]);Rsum+=A[u];
		int a=*R.begin();R.erase(R.begin());Rsum-=a;
		L.insert(a);Lsum+=a;
	}
	else if(L.size()==R.size()+1)
	{
		L.insert(A[u]);Lsum+=A[u];
		auto it=L.end();it--;
		int a=*it;L.erase(it);Lsum-=a;
		R.insert(a);Rsum+=a;
	}
	else assert(false);
	assert(L.size()==R.size()||L.size()==R.size()+1);
	if(L.size()+R.size()<3)ans[u]=-1;
	else
	{
		assert(!R.empty());
		int mn=*L.begin(),mx=*R.rbegin();
		if(mn==mx)ans[u]=1;
		else
		{
			ans[u]=9e18;
			{//del min
				long long mid=*R.begin();
				long long ret=0;
				ret+=mid*(L.size()-1)-(Lsum-mn);
				ret+=Rsum-mid*R.size();
				if(mid==mn)
				{
					ret+=cnt[mid]-1;
					ret-=(L.size()+R.size())-cnt[mid];
					ans[u]=min(ans[u],ret);
				}
				else
				{
					assert(mid>mn);
					ans[u]=min(ans[u],ret);
				}
			}
			{//del max
				int mx=*R.rbegin();
				long long mid=*L.rbegin();
				long long ret=0;
				ret+=mid*L.size()-Lsum;
				ret+=(Rsum-mx)-mid*(R.size()-1);
				if(mx==mid)
				{
					ret+=cnt[mid]-1;
					ret-=(L.size()+R.size())-cnt[mid];
					ans[u]=min(ans[u],ret);
				}
				else
				{
					assert(mx>mid);
					ans[u]=min(ans[u],ret);
				}
			}
		}
	}
	for(int v:G[u])if(v!=p)dfs(v,u);
	assert(L.size()==R.size()||L.size()==R.size()+1);
	assert(!L.empty());
	cnt[A[u]]--;
	if(*L.rbegin()>=A[u])
	{
		auto it=L.find(A[u]);
		assert(it!=L.end());
		L.erase(it);
		Lsum-=A[u];
		if(L.size()<R.size())
		{
			int a=*R.begin();R.erase(R.begin());Rsum-=a;
			L.insert(a);Lsum+=a;
		}
	}
	else
	{
		auto it=R.find(A[u]);
		assert(it!=R.end());
		R.erase(it);
		Rsum-=A[u];
		if(L.size()>R.size()+1)
		{
			auto it=L.end();it--;
			int a=*it;L.erase(it);Lsum-=a;
			R.insert(a);Rsum+=a;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=0;i<=N;i++)cin>>A[i];
	for(int i=1;i<=N;i++)
	{
		int u,v;cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	for(int i=1;i<=N;i++)cout<<ans[i]<<"\n";
}
0