求助帖,有题不会做
  • 板块学术版
  • 楼主Nahida831143
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/22 11:12
  • 上次更新2023/10/27 06:33:48
查看原帖
求助帖,有题不会做
846243
Nahida831143楼主2022/10/22 11:12

有道题不会做,求助一下各位大佬

题目描述

司傲鉴有一棵原本有 n 个节点 n - 1 条边的无根树,它的一些点被火烧了,一个点被烧了之后它与连接它的所有边都会消失。另外,他有 k 个节点防火,一定不会被烧。

司傲鉴现在给出它的原始形态与 k 个防火节点的编号,让你求出所有的 2 ^ (n - k) 种烧点方案所得的森林的连通块数量总和对 998244353 取模的值。

输入格式

第一行两个整数 n, k 。

第二行 k 个整数表示所有防火节点的坐标。(如果 k = 0则该行为空)

第三行到第 n + 1行每行两个整数 ,表示树上有一条连接 (u, v) 的边。

输出格式

一行一个整数表示答案。

输入输出样例

输入 #1

2 1

1

1 2

输出 #1

2

输入 #2

5 1

5

1 2

1 3

2 4

2 5

输出 #2

28

这个样例保证树是一条链。

样例解释

对于样例 ,有 2 ^ 1 = 2 种烧点方案,分别是:

不烧,有 1 个连通块。

烧掉 2 ,有 1 个连通块。 答案为 1 + 1 = 2 。

对于 100% 的数据,满足 n ≥ 1, 0 ≤ k ≤ n,给出的k个编号互不重复

2022/10/22 11:12
加载中...