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 <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k steps. Calculate the most number of different leaves that can be visited.
## Solution
Let's define some variables:
* <math><semantics><mrow><msub><mi>d</mi><mi>u</mi></msub></mrow><annotation encoding="application/x-tex">d_u</annotation></semantics></math>du - Depth of node <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u
* <math><semantics><mrow><msub><mi>h</mi><mi>u</mi></msub></mrow><annotation encoding="application/x-tex">h_u</annotation></semantics></math>hu - Lowest node that can be backtracked from leaves in subtree of <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u
* <math><semantics><mrow><msub><mi>f</mi><mi>u</mi></msub></mrow><annotation encoding="application/x-tex">f_u</annotation></semantics></math>fu - The maximum number of different leaves that can be visited staring from <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u
* <math><semantics><mrow><msub><mi>g</mi><mi>u</mi></msub></mrow><annotation encoding="application/x-tex">g_u</annotation></semantics></math>gu - The same as <math><semantics><mrow><msub><mi>f</mi><mi>u</mi></msub></mrow><annotation encoding="application/x-tex">f_u</annotation></semantics></math>fu, except that after visiting the leaves, it must be possible to backtrack to <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u's parent

The **state-transition equations** will be:
* If <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u is a leaf, <math><semantics><mrow><msub><mi>h</mi><mi>u</mi></msub><mo>=</mo><msub><mi>d</mi><mi>u</mi></msub><mo>−</mo><mi>k</mi><mo separator="true">,</mo><mtext> </mtext><msub><mi>f</mi><mi>u</mi></msub><mo>=</mo><msub><mi>g</mi><mi>u</mi></msub><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">h_u = d_u - k,\ f_u = g_u = 1</annotation></semantics></math>hu=du−k, fu=gu=1
* <math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math>v is child of <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u:
 * <math><semantics><mrow><msub><mi>h</mi><mi>u</mi></msub><mo>=</mo><mi>m</mi><mi>i</mi><msub><mi>n</mi><mi>v</mi></msub><mo>(</mo><msub><mi>h</mi><mi>v</mi></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">h_u = min_v (h_v)</annotation></semantics></math>hu=minv(hv)
 * <math><semantics><mrow><msub><mi>g</mi><mi>u</mi></msub><mo>=</mo><mrow><mo fence="true">{</mo><mtable><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>0</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mspace width="1em"></mspace><msub><mi>d</mi><mi>u</mi></msub><mo>≥</mo><msub><mi>h</mi><mi>u</mi></msub></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><msub><mo>∑</mo><mi>v</mi></msub><msub><mi>g</mi><mi>v</mi></msub></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mspace width="1em"></mspace><mi>e</mi><mi>l</mi><mi>s</mi><mi>e</mi></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex">g_u = \begin{cases} 0 &amp;\quad d_u \ge h_u \\ \sum_v g_v &amp;\quad else \end{cases}</annotation></semantics></math>gu={0∑vgvdu≥huelse
 * <math><semantics><mrow><msub><mi>f</mi><mi>u</mi></msub><mo>=</mo><msub><mo>∑</mo><mi>v</mi></msub><msub><mi>g</mi><mi>v</mi></msub><mo>+</mo><mi>m</mi><mi>a</mi><msub><mi>x</mi><mi>v</mi></msub><mo>(</mo><msub><mi>f</mi><mi>v</mi></msub><mo>−</mo><msub><mi>g</mi><mi>v</mi></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">f_u = \sum_v g_v + max_v(f_v-g_v)</annotation></semantics></math>fu=∑vgv+maxv(fv−gv)

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)

コメント

コメントを投稿