#1161462 (C++23) No.3514 Majority Driven Tree

• 問題: No.3514 Majority Driven Tree
• ユーザー: askr58
• 提出日時: 2026-04-24 22:54:57
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,013 bytes
• コンパイル時間: 4,517 ms
• コンパイル使用メモリ: 361,416 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-24 22:55:13
• 合計ジャッジ時間: 4,220 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 25 WA * 12

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<vector<int>> graph(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	if(n<=3){
		cout<<1<<endl;
		return 0;
	}
	vector<vector<array<int,2>>> dp(n);
	int inf=1e9;
	{
		auto dfs=[&](auto dfs,int v,int par)->array<int,2>{
			dp[v].resize(graph[v].size(),{inf,inf});
			int sum=0;
			vector<int> vec;
			for(int i=0;i<graph[v].size();i++){
				int u=graph[v][i];
				if(u==par)continue;
				dp[v][i]=dfs(dfs,u,v);
				sum+=dp[v][i][0];
				vec.push_back(dp[v][i][1]-dp[v][i][0]);
			}
			if(sum==0){
				return {1,0};
			}
			ranges::sort(vec);
			array<int,2> res={inf,inf};
			{
				int t=1;
				for(int x:vec)t+=x;
				res[0]=min(res[0],sum+t);
				res[1]=min(res[1],sum+t);
			}
			{
				int m=(graph[v].size()+2)/2;
				if(vec.size()>=m){
					int t=0;
					for(int i=0;i<vec.size()-m;i++)t+=vec[i];
					res[0]=min(res[0],t+sum);
				}
			}
			{
				int m=graph[v].size()/2;
				if(vec.size()>=m){
					int t=0;
					for(int i=0;i<vec.size()-m;i++)t+=vec[i];
					res[1]=min(res[1],t+sum);
				}
			}
			return res;
		};
		dfs(dfs,0,-1);
	}
	{
		auto dfs=[&](auto dfs,int v,int par,array<int,2> val)->void{
			if(par!=-1){
				for(int i=0;i<graph[v].size();i++){
					int u=graph[v][i];
					if(u==par)dp[v][i]=val;
				}
			}
			int sum=0,sum2=0;
			set<int> s1,s2;
			int m=graph[v].size()/2;
			vector<int> vec(graph[v].size());
			for(int i=0;i<graph[v].size();i++){
				sum+=dp[v][i][0];
				sum2+=dp[v][i][1];
				vec[i]=dp[v][i][1]-dp[v][i][0];
			}
			ranges::sort(vec,greater{});
			int t1=0,t2=0;
			int u1=0,u2=0;
			for(int i=0;i<=min((int)graph[v].size()-1,m+1);i++){
				if(i<m){
					t1+=vec[i];
					s1.insert(vec[i]);
				}
				if(i==m)u1=vec[i];
				t2+=vec[i];
				s2.insert(vec[i]);
				if(i==m+1)u2=vec[i];
			}
			for(int i=0;i<graph[v].size();i++){
				int u=graph[v][i];
				if(u==par)continue;
				array<int,2> arr={1+sum2-dp[v][i][1],1+sum2-dp[v][i][1]};
				if(m+2<=graph[v].size()){
					if(s2.count(dp[v][i][1]-dp[v][i][0])){
						arr[0]=min(arr[0],sum2-(t2-(dp[v][i][1]-dp[v][i][0])+u2));
					}else{
						arr[0]=min(arr[0],sum2-t2);
					}
				}
				if(m+1<=graph[v].size()){
					if(s1.count(dp[v][i][1]-dp[v][i][0])){
						arr[1]=min(arr[1],sum2-(t1-(dp[v][i][1]-dp[v][i][0])+u1));
					}else{
						arr[1]=min(arr[1],sum2-t1);
					}
				}
				dfs(dfs,u,v,arr);
			}
		};
		dfs(dfs,0,-1,{inf,inf});
	}
	int ans=inf;
	for(int i=0;i<n;i++){
		{
			int sum=0;
			for(auto[x,y]:dp[i])sum+=y;
			ans=min(ans,sum+1);
		}
		int m=graph[i].size()/2+1;
		if(m<=graph[i].size()){
			vector<int> vec;
			int sum=0;
			for(auto[x,y]:dp[i]){
				sum+=x;
				vec.push_back(y-x);
			}
			ranges::sort(vec);
			for(int i=0;i<graph[i].size()-m;i++)sum+=vec[i];
			ans=min(ans,sum);
		}
	}
	cout<<ans<<endl;
}