[CEOI 2021] Wells

Luogu

IDLGP8176

Time10000ms

Memory1024MB

DifficultyP7

2021CEOI（中欧）

给出一个有 $N$ 个结点的树和一个正整数 $K$，确定是否存在一个顶点子集，使得任意恰好包含 $K$ 个顶点的路径都**恰好**有一个来自该子集的顶点。此外，您需要找到模 $10^9+7$ 的此类子集的数量（不存在则为 $0$）。 ## Input 第一行两个整数 $N$ 和 $K$。接下来 $N-1$ 行，每行两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间存在一条无向边。 ## Output 第一行一个字符串，如果存在输出 `YES`，否则输出 `NO`。第二行输出一个整数，表示满足条件的子集个数，如果不存在，输出 $0$。 [samples] ## Background 译自 CEOI2021 Day2 T3. [Wells](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf)。 **滥用评测资源将被封号。** ## Note #### 样例解释1 ![](https://cdn.luogu.com.cn/upload/image_hosting/5v4lswx9.png) 满足条件的子集有：$\{3\}$，$\{1,2,4\}$。 #### 样例解释2 ![](https://cdn.luogu.com.cn/upload/image_hosting/hgp8ggz4.png) #### 样例解释3 ![](https://cdn.luogu.com.cn/upload/image_hosting/xv206wxg.png) 只有一条长度为 $5$ 的路径，该路径包含节点 $3,6,4,2,5$。这些节点中必须恰好有一个在子集中，并且节点 $1$ 是否在子集中没有区别。因此所有满足条件的子集有：$\{3\}$，$\{1,3\}$，$\{6\}$，$\{1,6\}$，$\{4\}$，$\{1,4\}$，$\{2\}$，$\{1,2\}$，$\{5\}$，$\{1,5\}$。 #### 数据范围与约定对于 $100\%$ 的数据：$2\leq K\leq N\le 1.5\times 10^6$。 | 子任务 | 分值 | 约束 | | :----: | :--: | :---------------------------------------------------: | | $1$ | $30$ | $2\leq K\leq N\le 200$ | | $2$ | $20$ | $2\leq K\leq N\le 10^4$ | | $3$ | $20$ | $2\leq K\leq N\le 5\times 10^5$ | | $4$ | $30$| $2\leq K\leq N\le 1.5\times 10^6$ |

Samples

Input #1

Output #1

YES 
2

Input #2

Output #2

NO
0

Input #3

Output #3

YES
10

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2021] Wells",
    "description": {
      "content": "给出一个有 $N$ 个结点的树和一个正整数 $K$，确定是否存在一个顶点子集，使得任意恰好包含 $K$ 个顶点的路径都**恰好**有一个来自该子集的顶点。此外，您需要找到模 $10^9+7$ 的此类子集的数量（不存在则为 $0$）。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8176"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个有 $N$ 个结点的树和一个正整数 $K$，确定是否存在一个顶点子集，使得任意恰好包含 $K$ 个顶点的路径都**恰好**有一个来自该子集的顶点。此外，您需要找到模 $10^9+7$ 的此类子集的数量（不存在则为 $0$）。\n\n## Input\n\n第一行两个整数 $N$ 和 $K$。\n\n接下来 $N-1$ 行，每行两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间存在一条...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments