A50544.BFS
普及+/提高
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
Alice 现在开始学习了 BFS , 他的伪代码如下:
# 假设图使用邻接表表示,adjList[i] 存储顶点 i 的所有邻接顶点
adjList = [] # 邻接表
n = len(adjList) # 顶点数量
visited = [False] * n # 标记顶点是否已被访问
def BFS(s):
queue = [] # 用于 BFS 的队列
queue.append(s) # 将起始顶点加入队列
visited[s] = True # 标记起始顶点已访问
while queue: # 当队列不为空时,继续循环
u = queue.pop(0) # 取出队首顶点
for v in adjList[u]: # 遍历顶点 u 的所有邻接顶点 v
if not visited[v]: # 如果邻接顶点 v 未被访问
queue.append(v) # 将未访问的邻接顶点加入队列
visited[v] = True # 标记为已访问
return visited
在标准的 BFS 中,节点从队列中弹出的顺序称为 BFS 序。例如,对于一棵具有 4 个节点的树,边为 (1,2)、(1,3)、(2,4),一种可能的 BFS 序是 [1,2,3,4](假设从节点 1 开始)。
然而,Alice 的队列实现出现了一些问题:每次从队列中弹出元素时,她不再是严格按照先进先出的顺序,而是随机从队列中弹出一个元素。现在,Alice 想知道:对于一棵给定的树,从某个起点出发,所有可能的"随机 BFS 序"有多少种,结果可能很大 ,请将结果对 998244353 取模。
输入格式
第一行输入一个整数 n ,代表树的结点数。
接下来 n−1 行,每行给出两个整数 ui,vi ,代表两个结点之间存在着一条边。
输出格式
输出 n 行,第 i 行代表从第 i 号节点开始,可能的"随机 BFS 序"有多少种.
输入输出样例
输入#1
4 1 2 1 3 2 4
输出#1
3 3 1 1
输入#2
7 1 2 1 3 1 4 2 5 3 6 3 7
输出#2
120 48 90 20 8 15 15
说明/提示
数据范围
- 1≤n≤106
- 1≤ui,vi≤n
- 保证树合法
样例解释
对于样例 1 , 从 1 开始, 可能的 BFS 序有三种 , 分别为 {1,2,3,4} , {1,3,2,4}, {1,2,4,3}