Latex
查看原帖
Latex
378996
UncleSam_Died楼主2023/12/29 20:46

你有一棵带有 nn 个结点的树,根是结点 11。有一个标记,最初在根结点处。你可以将标记移动到其他结点处。假设标记当前所在结点为 vv,你可以做出以下两种操作:

  1. 将标记移动到 vv 子树的任一叶子处。
  2. 如果是结点 vv 为叶子,则将标记向根移动不超过 kk 次。换句话说,如果 hvh_v 为结点 vv 的深度 (根的深度为 00),你可以将其移动到顶点 toto(toto 为 vv 祖先)并且 hv−k≤htoh_v−k\le h_{to}。

根不是叶子(即使它的度数是 11)。计算最多能访问多少叶子。

输入格式:

  • 第一行包含两个整数 nn 和 kk(1≤k<n≤1061\le k<n\le 10^6) ——树中的顶点数和向上移动的限制。

  • 第二行包含 n−1n-1个整数,第 ii 个整数表示结点 i+1i+1 的父亲。输入保证树合法,根为 11。

输出格式:

输出一个整数,表示可以访问的最大叶子数。

你有一棵带有 $n$ 个结点的树,根是结点 $1$。有一个标记,最初在根结点处。你可以将标记移动到其他结点处。假设标记当前所在结点为 $v$,你可以做出以下两种操作:
1. 将标记移动到 $v$ 子树的任一叶子处。
2. 如果是结点 $v$ 为叶子,则将标记向根移动不超过 $k$ 次。换句话说,如果 $h_v$ 为结点 $v$ 的深度 (根的深度为 $0$),你可以将其移动到顶点 $to$($to$ 为 $v$ 祖先)并且 $h_v−k\le h_{to}$。

根不是叶子(即使它的度数是 $1$)。计算最多能访问多少叶子。
#### 输入格式:
- 第一行包含两个整数 $n$ 和 $k$($1\le k<n\le 10^6$) ——树中的顶点数和向上移动的限制。

- 第二行包含 $n-1$个整数,第 $i$ 个整数表示结点 $i+1$ 的父亲。输入保证树合法,根为 $1$。
#### 输出格式:
输出一个整数,表示可以访问的最大叶子数。
2023/12/29 20:46
加载中...