Back to : problem-solving

๋ฌธ์ œ ๋งํฌ
๋‚œ์ด๋„ : ๊ธฐ์ค€ Platinum 4.


๊ฒฐ๊ตญ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋Š”, ์–ด๋–ค ํŠธ๋ฆฌ๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ํŠธ๋ฆฌ์—์„œ ์ตœ๋Œ€ $K$๊ฐœ์˜ path๋ฅผ ํƒํ•˜์—ฌ ๊ทธ path๋“ค์˜ union์„ ์ตœ๋Œ€ํ™”ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋ฌธ์ œ์˜ ํŠน์„ฑ ์ƒ, ํŠธ๋ฆฌ DP๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
dp[i][j] : $i$๋ฒˆ์งธ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” subtree์— ๋Œ€ํ•ด, $j$๊ฐœ์˜ path๋ฅผ ํƒํ–ˆ์„ ๋•Œ์˜ ์ตœ๋Œ“๊ฐ’

์ด DP๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ๋งŒ์•ฝ ๋‚ด child node์— ๋Œ€ํ•ด ๋ชจ๋“  dp๊ฐ’์„ ์•Œ๊ณ  ์žˆ๋‹ค๋ฉด, ๋‚ด child node ๋“ค์— ๋Œ€ํ•ด ๊ฐ ๋…ธ๋“œ๋‹น ๋ช‡๊ฐœ์˜ chain์„ ์‚ฌ์šฉํ• ์ง€๋ฅผ ์ •ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋Š” ๊ตณ์ด ์—ด์‹ฌํžˆ ๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•ด ๋ณด์ง€ ์•Š๋”๋ผ๋„, ์ ์–ด๋„ $O(NK)$ ์นธ์˜ DP๋ฅผ ๋ชจ๋‘ ์ฑ„์›Œ์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ „ํ˜€ ๋‹ต์ด ์—†์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 3๊ฐœ์˜ ์ž์‹๋…ธ๋“œ๋ฅผ ๊ฐ€์ง„ ๋…ธ๋“œ์— ๋Œ€ํ•ด dp[i][5]๋ฅผ ๊ณ„์‚ฐํ•˜๋ ค๋ฉด, 5๋ฅผ 3๊ฐœ๋กœ ๋ถ„ํ• ํ•˜๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์— ๋Œ€ํ•ด ๊ฐ๊ฐ dp๊ฐ’์„ ๋”ํ•ด์„œ ํ™•์ธํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— exponentialํ•œ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆด ๊ฒƒ์ž…๋‹ˆ๋‹ค.

๋Œ€์‹ ํ•ด์„œ, ์ด๋ ‡๊ฒŒ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์ดํ•˜, ํ•œ์ค„๋กœ ์ญ‰ ์—ฐ๊ฒฐ๋œ path๋ฅผ ๊ฒฝ๋กœ ๋˜๋Š” ์ฒด์ธ์œผ๋กœ ํ‘œํ˜„ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

  • ๋งŒ์•ฝ ์ตœ์ข…์ ์ธ ๋‹ต์ด, ํŠธ๋ฆฌ์—์„œ ๊ฐ€์žฅ ๊ธด ๊ฒฝ๋กœ (๋ฃจํŠธ-๋ฆฌํ”„ ์ค‘ ๊ฐ€์žฅ ๊ธด ๊ฒฝ๋กœ)๋ฅผ ํฌํ•จํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ์ ๋‹นํ•œ ๊ฒฝ๋กœ ํ•˜๋‚˜๋ฅผ ๋นผ๊ณ  ๋Œ€์‹ ์— ์ด ๊ฐ€์žฅ ๊ธด ๊ฒฝ๋กœ๋ฅผ ์ง‘์–ด๋„ฃ์œผ๋ฉด ๋” ์ข‹์€ ๋‹ต์ด ๋ฉ๋‹ˆ๋‹ค.
  • ์ด๋ฅผ ๊ท€๋‚ฉ์ ์œผ๋กœ ๋ฐ˜๋ณต ์ ์šฉํ•˜๋ฉด, ๋ฌด์กฐ๊ฑด ํ˜„์žฌ ๋‚จ์•„ ์žˆ๋Š” ๊ฐ€์žฅ ๊ธด ๊ฒฝ๋กœ๋ฅผ ํƒํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  • ๋‹จ, path์˜ ๊ธธ์ด์˜ ํ•ฉ์ด ์•„๋‹ˆ๋ผ union์— ํฌํ•จ๋œ ๋…ธ๋“œ ์ˆ˜๋ฅผ ์„ธ๊ธฐ ๋•Œ๋ฌธ์—, ์ด๋ฏธ ํ•œ๋ฒˆ ๋ฐฉ๋ฌธ๋œ ๋…ธ๋“œ๋Š” ๋”์ด์ƒ path์˜ ๊ธธ์ด์— ์˜๋ฏธ๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

path์˜ ๊ฐœ์ˆ˜๋Š” ๋„ˆ๋ฌด ๋งŽ๊ณ , ์šฐ๋ฆฌ๋Š” ์–ด์ฐจํ”ผ ์–ด๋–ค ๋…ธ๋“œ๋ฅผ ์ •ํ•˜๋ฉด ๊ฑฐ๊ธฐ์„œ๋ถ€ํ„ฐ ๋ฆฌํ”„๊นŒ์ง€ ๋‹ฌ๋ ค๊ฐ€๋Š”๊ฒŒ ์ตœ๋Œ€ํ•œ ์ด๋“์ด๊ธฐ ๋•Œ๋ฌธ์—, โ€œ์–ด๋–ค ๋…ธ๋“œ๋ฅผ ๊ณจ๋ผ์„œโ€ ๊ทธ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ ๊ฐ€์žฅ ๊นŠ์ด ๋“ค์–ด๊ฐ€ ์žˆ๋Š” ๋ฆฌํ”„๊นŒ์ง€์˜ ๊ฒฝ๋กœ๋ฅผ ํƒํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋„ ์ถฉ๋ถ„ํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, ํŠธ๋ฆฌ๋ฅผ ์„œ๋กœ disjointํ•œ path๋กœ ์ž˜๋ผ์„œ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

์ด์ œ, ๋ฏธ๋ฆฌ ๋ชจ๋“  path๋ฅผ priority queue์— ๋„ฃ์–ด๋†“๊ณ , ์ด๋ฅผ ๊ณ ๋ฅด๋Š” ์‹์œผ๋กœ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ๋‹จ, ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋Š” ๋‹ค์‹œ ๊ณ ๋ฅด์ง€ ์•Š๋„๋ก ์กฐ์ •ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์•„๋ž˜ ๊ตฌํ˜„์ด ์ถฉ๋ถ„ํžˆ ์ง๊ด€์ ์œผ๋กœ ์ฝํžŒ๋‹ค๊ณ  ์ƒ๊ฐํ•ด์„œ, ๋”์ด์ƒ ์„ค๋ช…์€ ์ƒ๋žตํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.


#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int N, K;
vector <int> T[101010];
int depth[101010];
bool vst[101010];
struct path {
    int head;
    int length;
    int tail;
    bool operator<(const path &o) const {
        return length < o.length;
priority_queue<path> pq;
path dfs(int r, int p) {
    depth[r] = depth[p] + 1;
    path longest_path;
    longest_path.length = 1;
    longest_path.head = r;
    longest_path.tail = r;
    for (int c : T[r]) {
        if (c == p) continue;
        path child_path = dfs(c, r);
        if (child_path.length + 1 > longest_path.length) {
            longest_path.length = child_path.length + 1;
            longest_path.tail = child_path.tail;
    return longest_path;

int parent[101010];
int32_t main() {
    cin >> N >> K;
    for (int i = 2; i <= N; i++) {
        int x; cin >> x;
        parent[i] = x;
    dfs(1, 0);
    int ans = 0;
    while (!pq.empty() and K) {
        auto longest =;
        if (vst[longest.head]) continue;
        ans += longest.length;
        K -= 1;
        for (int cur = longest.tail; cur != longest.head; cur = parent[cur]) {
            vst[cur] = true;
        vst[longest.head] = true;
    cout << ans << '\n';