Submission #1174610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174610		hengliao	Balanced Tree (info1cup18_balancedtree)	C++20	13 / 100	164 ms	15740 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 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(c[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(1, 0);
    // 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[1]>-inf) return false;
    dumb=1;
    dfs(1, 0);
    // 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[1]>-inf) return false;
    return true;
}

void solve(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        adj[i].clear();
    }
    for(ll i=0;i<n-1;i++){
        ll u, v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(ll i=1;i<=n;i++){
        cin>>c[i];
    }
    // 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: 0 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6