Codeforces 1065F. Up and Down the Tree (DP + Tree + Greedy)

日付: 12月 19, 2018

[Problem - 1065F - Codeforces](https://codeforces.com/contest/1065/problem/F)
## Problem
Given a tree with root at 1, initially a token is at root, you can either move the token down to some leaf or move up from a leaf by at most $k$ steps. Calculate the most number of different leaves that can be visited.
## Solution
Let's define some variables:
* $d_u$ - Depth of node $u$
* $h_u$ - Lowest node that can be backtracked from leaves in subtree of $u$
* $f_u$ - The maximum number of different leaves that can be visited staring from $u$
* $g_u$ - The same as $f_u$, except that after visiting the leaves, it must be possible to backtrack to $u$'s parent

The **state-transition equations** will be:
* If $u$ is a leaf, $h_u = d_u - k,\ f_u = g_u = 1$
* $v$ is child of $u$:
 * $h_u = min_v (h_v)$
 * $g_u = \begin{cases} 0 &\quad d_u \ge h_u \\ \sum_v g_v &\quad else \end{cases}$
 * $f_u = \sum_v g_v + max_v(f_v-g_v)$

The key **observation** is that: If backtracking to parent is needed, it is always better to use the child which can reach lowest depth as the last one.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

const int N = 1e6 + 5;
int n, k, F[N][2], H[N], D[N];
vector<int> G[N];

void dfs(int u, int d) { D[u] = d; for (auto v : G[u]) dfs(v, d + 1); }
void dp(int u) {
    if (G[u].empty()) { H[u] = D[u] - k; F[u][0] = F[u][1] = 1; return; }
    F[u][0] = F[u][1] = 0;
    int tmp = 0, tv = -1;
    for (auto v : G[u]) {
        dp(v);
        H[u] = min(H[u], H[v]);
        F[u][0] += F[v][1], F[u][1] += F[v][1];
        if (F[v][0] - F[v][1] > tmp) tmp = F[v][0] - F[v][1], tv = v;
    }
    if (tv != -1) F[u][0] += tmp;
    if (H[u] >= D[u]) F[u][1] = 0;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 2, j; i <= n; i++) scanf("%d", &j), G[j].push_back(i);
    dfs(1, 0);
    memset(H, 10, sizeof H);
    dp(1);
    printf("%d\n", F[1][0]);
    return 0;
}
```

KONGROOの基地

このブログを検索

Codeforces 1065F. Up and Down the Tree (DP + Tree + Greedy)

コメント

コメントを投稿