제출 #1260682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260682		DangKhoizzzz	Cat in a tree (BOI17_catinatree)	C++20	11 / 100	1095 ms	7800 KiB

catinatree

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int maxn = 3e5 + 7;

int n, D, dep[maxn], jump[maxn][23];
vector <int> g[maxn];
vector <int> chosen;

int leaf = 1;

void dfs(int u, int p)
{
    if(g[u].size() == 1) leaf = u;

    for(int v: g[u])
    {
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        jump[v][0] = u;
        dfs(v, u);
    }
}

void build()
{
    dep[0] = -1;
    dfs(1, 1);
    for(int j = 1; j <= 19; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v)
{
    if(dep[u] > dep[v]) return lca(v, u);

    for(int i = 20; i >= 0; i--)
    {
        if(dep[jump[v][i]] >= dep[u])
        {
            v = jump[v][i];
        }
    }
    if(u == v) return u;

    for(int i = 20; i >= 0; i--)
    {
        if(jump[v][i] != jump[u][i])
        {
            v = jump[v][i];
            u = jump[u][i];
        }
    }
    return jump[u][0];
}

int dist(int u, int v)
{
    return dep[u] + dep[v] - 2*dep[lca(u, v)];
}


void dfs_ans(int u, int p)
{
    for(int v: g[u])
    {
        if(v == p) continue;
        dfs_ans(v, u);
    }
    bool add = true;
    for(int node: chosen)
    {
        if(dist(node, u) < D) add = false;
    }
    if(add) chosen.push_back(u);
}

void solve()
{
    cin >> n >> D;
    for(int i = 1; i < n; i++)
    {
        int v;
        cin >> v;
        g[i+1].push_back(v+1);
        g[v+1].push_back(i+1);
    }
    build();
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        dfs_ans(i , i);
        ans = max(ans , (int)chosen.size());
        chosen.clear();
    }
    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49