/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 9.414 MiB
#2 Accepted 4ms 9.277 MiB
#3 Accepted 4ms 9.32 MiB
#4 Accepted 4ms 9.027 MiB
#5 Accepted 51ms 16.754 MiB
#6 Accepted 55ms 16.387 MiB
#7 Accepted 58ms 16.828 MiB
#8 Accepted 88ms 16.793 MiB
#9 Accepted 65ms 15.566 MiB
#10 Accepted 65ms 16.609 MiB
#11 Accepted 71ms 16.02 MiB
#12 Accepted 68ms 15.52 MiB
#13 Accepted 131ms 16.043 MiB
#14 Accepted 112ms 16.02 MiB
#15 Accepted 124ms 16.051 MiB
#16 Accepted 126ms 16.051 MiB
#17 Accepted 122ms 16.059 MiB
#18 Accepted 115ms 16.02 MiB
#19 Accepted 64ms 15.746 MiB
#20 Accepted 66ms 22.102 MiB
#21 Accepted 77ms 28.023 MiB
#22 Accepted 5ms 9.027 MiB
#23 Accepted 4ms 8.668 MiB
#24 Accepted 4ms 8.527 MiB

Code

#include<bits/stdc++.h>
using namespace std;
const long long M=2e5+10,MOD=998244353;
typedef long long ll;
#define debug(x) cout<<x<<endl
int level[M];
int dp[M][2];
int low[M];
int up[M];
int mx=0;
int n,k;
int bonus[M];
vector<int>edge[M];
void dfs1(int x,int p){
    for(auto it:edge[x]){
        if(it!=p){
            up[it]=up[x]+1;
            if(x==1){
                low[it]=dp[x][0];
                if(dp[x][0]==level[it]+1)low[it]=dp[x][1];
                low[it]--;
                low[it]=max(low[it],0);
            }
            else{
                low[it]=low[x];
                int cur=dp[x][0];
                if(dp[x][0]==level[it]+1)cur=dp[x][1];
                cur-=1;
                cur=max(0,cur);
                bonus[it]=bonus[x];
                bonus[it]+=cur;
                mx=max(mx,up[it]+min(low[x]+bonus[it],k));
            }
            dfs1(it,x);
        }
    }
}
void dfs(int x,int p){
    for(auto it:edge[x]){
        if(it!=p){
            dfs(it,x);
        }
    }
    level[p]=max(level[p],level[x]+1);
    if(dp[p][0]<level[p]){
        swap(dp[p][0],dp[p][1]);
        dp[p][0]=level[p];
    }
    else if(level[x]+1>dp[p][1])dp[p][1]=level[x]+1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
   // cin>>t;
    while(t--){
       //int n,k;
       cin>>n>>k;
       for(int i=1;i<=n;i++)level[i]=1;
       for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
       }
       dp[1][0]=1;
       dfs(1,0);
       mx=dp[1][0];
       up[1]=1;
       mx+=min(max(0,dp[1][1]-1),k);
       dfs1(1,0);
       cout<<min(mx,n)<<"\n";

    }
    

    
    return 0;
 
}

Information

Submit By
Type
Submission
Problem
P1111 Thakurs tree game
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-21 22:32:49
Judged At
2024-11-07 09:23:53
Judged By
Score
100
Total Time
131ms
Peak Memory
28.023 MiB