[JRKSJ R7] 茎

Luogu

IDLGP8935

Time1000ms

Memory128MB

DifficultyP6

2023洛谷原创O2优化背包 DP树形 DP

你有一棵 $n$ 个点的根节点为 $1$ 的有根树，现在你要对这棵树进行剪枝，每次你可以选择一个还未被剪掉的节点 $u$ 进行操作，然后剪掉 $u$ 的子树所有点（包括 $u$）。当且仅当你剪掉 $1$ 时，操作停止。你知道 $1$ 到 $x$ 这条路径是这棵树的茎，需要特殊处理。所以你需要在第 $k$ 次剪枝时对 $x$ 进行操作，而非仅仅将其剪掉，即你不能在第 $k$ 次及以前对其祖先进行操作使其被连带剪掉。求有多少种不同的操作序列，两个操作序列不同当且仅当长度不同或存在一次操作 $i$ 使得两操作序列在第 $i$ 次时选择的 $u$ 不同。输出答案模 $10^9+7$。 ## Input 第一行三个数 $n,k,x$。接下来 $n-1$ 行每行两个数 $u,v$，代表树上的一条边 $(u,v)$。 ## Output 一个数表示答案对 $10^9+7$ 取模的结果。 [samples] ## Note ### 样例解释对于样例 $1$，只有一种操作方法满足条件，第一次操作 $3$，第二次操作 $2$，第三次操作 $1$。对于样例 $2$，满足条件的操作序列：$\{3,4,1\},\{3,4,2,1\},\{3,4,5,1\},\{3,4,5,2,1\},\\ \{5,4,1\},\{5,4,2,1\},\{5,4,2,3,1\},\{5,4,3,1\},\{5,4,3,2,1\}$。 ### 数据规模本题采用捆绑测试。 |$\text{Subtask}$|$n\le$|特殊性质|$\text{Score}$| |:-:|:-:|:-:|:-:| |$1$|$7$|无|$5$| |$2$|$17$|无|$10$| |$3$|$50$|$\text A$|$5$| |$4$|$50$|无|$15$| |$5$|$500$|$\text A$|$5$| |$6$|$500$|$\text B$|$5$| |$7$|$500$|$\text C$|$10$| |$8$|$500$|无|$45$| 特殊性质 $\text A$：保证 $k=1$。\ 特殊性质 $\text B$：保证 $x=1$。\ 特殊性质 $\text C$：保证 $\forall i\in[1,n-1],i$ 与 $i+1$ 有边。对于 $100\%$ 的数据，$1\le k,x\le n\le 500$。

Samples

Input #1

3 2 2
1 2
1 3

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[JRKSJ R7] 茎",
    "description": {
      "content": "你有一棵 $n$ 个点的根节点为 $1$ 的有根树，现在你要对这棵树进行剪枝，每次你可以选择一个还未被剪掉的节点 $u$ 进行操作，然后剪掉 $u$ 的子树所有点（包括 $u$）。当且仅当你剪掉 $1$ 时，操作停止。   你知道 $1$ 到 $x$ 这条路径是这棵树的茎，需要特殊处理。所以你需要在第 $k$ 次剪枝时对 $x$ 进行操作，而非仅仅将其剪掉，即你不能在第 $k$ 次及以前对其祖先",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8935"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一棵 $n$ 个点的根节点为 $1$ 的有根树，现在你要对这棵树进行剪枝，每次你可以选择一个还未被剪掉的节点 $u$ 进行操作，然后剪掉 $u$ 的子树所有点（包括 $u$）。当且仅当你剪掉 $1$ 时，操作停止。  \n\n你知道 $1$ 到 $x$ 这条路径是这棵树的茎，需要特殊处理。所以你需要在第 $k$ 次剪枝时对 $x$ 进行操作，而非仅仅将其剪掉，即你不能在第 $k$ 次及以前对其祖先...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments