A50544.BFS

普及+/提高

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

AliceAlice 现在开始学习了 BFSBFS , 他的伪代码如下:

# 假设图使用邻接表表示,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

在标准的 BFSBFS 中,节点从队列中弹出的顺序称为 BFSBFS 序。例如,对于一棵具有 4 个节点的树,边为 (1,2)(1, 2)(1,3)(1, 3)(2,4)(2, 4),一种可能的 BFSBFS 序是 [1,2,3,4][1, 2, 3, 4](假设从节点 1 开始)。

然而,AliceAlice 的队列实现出现了一些问题:每次从队列中弹出元素时,她不再是严格按照先进先出的顺序,而是随机从队列中弹出一个元素。现在,AliceAlice 想知道:对于一棵给定的树,从某个起点出发,所有可能的"随机 BFSBFS 序"有多少种,结果可能很大 ,请将结果对 998244353998244353 取模。

输入格式

第一行输入一个整数 nn ,代表树的结点数。

接下来 n1n - 1 行,每行给出两个整数 ui,viu_i , v_i ,代表两个结点之间存在着一条边。

输出格式

输出 nn 行,第 ii 行代表从第 ii 号节点开始,可能的"随机 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
    

说明/提示

数据范围

  • 1n1061 \le n \le 10^6
  • 1ui,vin1 \le u_i ,v_i \le n
  • 保证树合法

样例解释
对于样例 11 , 从 11 开始, 可能的 BFSBFS 序有三种 , 分别为 {1,2,3,4}\{1 , 2 , 3 , 4\} , {1,3,2,4}\{1 , 3, 2 , 4\}, {1,2,4,3}\{1 , 2 , 4 , 3\}

首页