/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 548.0 KiB
#3 Wrong Answer 1ms 540.0 KiB
#4 Wrong Answer 1ms 540.0 KiB

Code

/**
 *  @author:   Binoy Barman
 *  @created:  2024-11-05 21:42:36
**/

#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
#define all(v) v.begin(), v.end()
#define Too_Many_Jobs int tts, tc = 1; cin >> tts; hell: while(tts--)
#define Dark_Lord_Binoy ios_base::sync_with_stdio(false); cin.tie(NULL);

#ifdef LOCAL
#include "debug/whereisit.hpp"
#else
#define dbg(...) 42
#endif
#define int long long

const int N = 2e5 + 9;

int ans = 0;

struct Dfs {
    int n, k;
    vector<int> pos, sz, lvl, dep;
    vector<vector<int>> g;
    Dfs(int _n, int _k) : n (_n), k (_k) {
        pos.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        lvl.assign(n + 1, 0);
        dep.assign(n + 1, 1);
        g.assign(n + 1, vector<int>());
    }
    void addEdge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u); 
    }
    void dfs(int v, int p = -1) {
        sz[v] = 1;
        int mx = 0, mx2 = 0;
        for(auto u : g[v]) {
            if(u == p) continue;
            lvl[u] = 1 + lvl[v];
            dfs(u, v);
            sz[v] += sz[u];
            dep[v] = max(dep[v], 1 + dep[u]);
            if(v == 1) {
                dbg(dep[u], u);
            }
            if(pos[u] >= mx) {
                mx2 = mx;
                mx = pos[u];
            } else if(pos[u] > mx2) {
                mx2 = pos[u];
            }
        }
        pos[v] = 1 + mx + mx2;
        dbg(v, pos[v], mx, mx2);
    }
    void dfs2(int v, int p = -1) {
        int mx = 0, mx2 = 0;
        for(auto u : g[v]) {
            if(u == p) continue;
            if(pos[u] >= mx) {
                mx2 = mx;
                mx = pos[u];
            } else if(pos[u] > mx2) {
                mx2 = pos[u];
            }
        }
        dbg(v, mx, mx2);
        ans = max(ans, mx + min(k, mx2 + 1));
        for(auto u : g[v]) {
            if(u == p) continue;
            dfs2(u, v);
        }
    }
};

int32_t main() {
Dark_Lord_Binoy
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, k;
    cin >> n >> k;
    Dfs g(n, k);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }
    ans = g.pos[1];
    g.dfs(1);
    g.dfs2(1);
    cout << ans << nl;

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1111 Thakurs tree game
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:36:14
Judged At
2024-11-05 16:36:14
Judged By
Score
5
Total Time
1ms
Peak Memory
548.0 KiB