Submission #1174647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174647		hengliao	Balanced Tree (info1cup18_balancedtree)	C++20	10 / 100	4094 ms	12872 KiB

balancedtree

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

const ll mxN=5e5+5;
const ll inf=1e9;

ll n;
vll adj[mxN];
ll c[mxN];
ll tep[mxN];
ll dp[mxN];
ll dp2[mxN];
ll tar;
ll dumb;

void dfs(ll cur, ll par){
    dp[cur]=-inf;
    dp2[cur]=inf;
    // if(c[cur]==-1){
    //     dp[cur][0][1][0]=0;
    //     dp[cur][1][1][0]=0;
    // }
    // else{
    //     dp[cur][c[cur]][1][0]=0;
    // }
    if(tep[cur]==dumb){
        dp2[cur]=0;
        dp[cur]=0;
    }
    for(auto &chd:adj[cur]){
        if(chd==par) continue;
        dfs(chd, cur);
        
        ll tep1=inf, tep2=inf;
        if(dp[cur]+dp2[chd]+1<=tar && dp[chd]+1+dp2[cur]<=tar){
            dp[cur]=-inf;
        }
        else if(dp[cur]+dp2[chd]+1<=tar){
            dp[cur]=dp[chd]+1;
        }
        else if(dp[chd]+1+dp2[cur]<=tar){

        }
        else{
            dp[cur]=max(dp[cur], dp[chd]+1);
        }
        dp2[cur]=min(dp2[cur], dp2[chd]+1);
    }
}

bool check(ll tt){
    tar=tt;
    dumb=0;
    dfs(0, -1);
    // cout<<"tar: "<<tar<<'\n';
    // cout<<"dumb: "<<dumb<<'\n';
    // for(ll i=1;i<=n;i++){
    //     cout<<"i: "<<i<<'\n';
    //     cout<<dp[i]<<' '<<dp2[i]<<'\n';
    // }
    if(dp[0]>-inf) return false;
    dumb=1;
    dfs(0, -1);
    // cout<<"tar: "<<tar<<'\n';
    // cout<<"dumb: "<<dumb<<'\n';
    // for(ll i=1;i<=n;i++){
    //     cout<<"i: "<<i<<'\n';
    //     cout<<dp[i]<<' '<<dp2[i]<<'\n';
    // }
    if(dp[0]>-inf) return false;
    return true;
}

void solve(){
    cin>>n;
    for(ll i=0;i<=n;i++){
        adj[i].clear();
    }
    for(ll i=0;i<n-1;i++){
        ll u, v;
        cin>>u>>v;
        u--; v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(ll i=0;i<n;i++){
        cin>>c[i];
    }
    ll ans=inf;
    ll good=-1;
    for(ll mask=0;mask<(1LL<<n);mask++){
        bool ok=1;
        for(ll i=0;i<n;i++){
            if((mask>>i)&1){
                if(c[i]==0){
                    ok=0;
                    break;
                }
                tep[i]=1;
            }
            else{
                if(c[i]==1){
                    ok=0;
                    break;
                }
                tep[i]=0;
            }
        }
        if(!ok) continue;
        ll lef=1, rig=n-1;
        ll cur=-1;
        while(lef<=rig){
            ll mid=(lef+rig)/2;
            if(check(mid)){
                cur=mid;
                rig=mid-1;
            }
            else{
                lef=mid+1;
            }
        }
        if(cur==-1) continue;
        if(cur<ans){
            ans=cur;
            good=mask;
        }
    }
    if(ans==inf){
        cout<<-1<<'\n';
        return;
    }
    cout<<ans<<'\n';
    for(ll i=0;i<n;i++){
        cout<<((good>>i)&1)<<' ';
    }
    cout<<'\n';
    // check(2);
    // ll lef=1, rig=n-1;
    // ll ans=-1;
    // while(lef<=rig){
    //     ll mid=(lef+rig)/2;
    //     if(check(mid)){
    //         ans=mid;
    //         rig=mid-1;
    //     }
    //     else{
    //         lef=mid+1;
    //     }
    // }
    // cout<<ans<<'\n';
    // if(ans==-1) return;
    // for(ll i=1;i<=n;i++){
    //     if(c[i]==-1 && i==4){
    //         cout<<1<<' ';
    //     }
    //     else if(c[i]==-1){
    //         cout<<0<<' ';
    //     }
    //     else{
    //         cout<<c[i]<<' ';
    //     }
    // }
    // cout<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6