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

• 問題: No.3514 Majority Driven Tree
• ユーザー: Yoyoyo8128
• 提出日時: 2026-04-16 10:41:42
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 3,657 bytes
• コンパイル時間: 3,744 ms
• コンパイル使用メモリ: 350,588 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-24 20:54:19
• 合計ジャッジ時間: 6,990 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 37

ソースコード

#pragma region Yoyoyo

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using i128t=__int128_t;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const string Yes="Yes";
const string No="No";
const long long inf=1ll<<60;

#ifndef LOCAL
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr);
#define print(s) cout<<s<<endl;

template<typename T>
inline bool chmax(T &a,T b){return ((a<b)?(a=b,true):(false));}
template<typename T>
inline bool chmin(T &a,T b){return ((a>b)?(a=b,true):(false));}
template<typename T>
ll sum(const T&a){return accumulate(all(a),0LL);}

template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U>&p){
    os<<p.first<<" "<<p.second;
    return os;
}

template<typename T,typename U>
istream &operator>>(istream &is,pair<T,U>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<(i?" ":"")<<v[i];
    }
    return os;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(auto &x:v){
        is>>x;
    }
    return is;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<T>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<v[i]<<endl;
    }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<vector<vector<T>>>&v){
    int s=v.size();
    for(int i=0;i<s;i++){
        os<<"i = "<<i<<endl;
        os<<v[i];
    }
    return os;
}

#ifdef LOCAL
template<class... Args>
void debug_out(Args... args){
    int _i=0;
    ((cerr<<(_i++?", ":" ")<<args), ...);
    cerr<<"\n";
}
#define debug(...){\
    cerr<<"["<<#__VA_ARGS__<<"]:";\
    debug_out(__VA_ARGS__);\
}
#else
#define debug(...)
#endif

#pragma endregion Yoyoyo


ll mod=998244353;


int main(){
    faster;
    ll N;
    cin>>N;
    {
        assert(1<=N && 1<=100000);
    }
    vector<vector<int>>G(N);
    vector<int>cnt(N);
    for(int i=0;i<N-1;i++){
        int u,v;
        cin>>u>>v;
        {assert(1<=u && v<=N);}
        u--;v--;
        cnt[u]++;cnt[v]++;
        G[u].pb(v);
        G[v].pb(u);
    }
    {assert(*min_element(all(cnt)));}
    vector<pll>dp(N,{1e9,1e9});
    //親依存、非親依存 a<=b
    auto dfs = [&](auto &&self,int s,int p)->void {
        //debug(s);
        for(auto e:G[s]){
            if(e==p)continue;
            self(self,e,s);
        }
        //1コスを使う場合
        {
            ll cos=1;
            for(auto e:G[s]){
                if(e==p)continue;
                cos+=dp[e].fi;
            }
            chmin(dp[s].se,cos);
        }
        //1コスを使わない場合
        {
            ll half=cnt[s]/2+1;
            vector<ll>cos(0);
            ll afi=0;
            for(auto e:G[s]){
                if(e==p)continue;
                cos.pb(dp[e].se-dp[e].fi);
                afi+=dp[e].fi;
            }
            
            sort(all(cos));
            for(int i=0;i<half-1;i++){
                afi+=cos[i];
            }
            chmin(dp[s].fi,afi);
            
            if(cos.size()>1 || s==0){
                afi+=cos[half-1];
                chmin(dp[s].se,afi);
            }
            
        }
        chmin(dp[s].fi,dp[s].se);
    };
    dfs(dfs,0,-1);
    debug(dp);
    cout<<dp[0].se<<"\n";
}