UOJ Logo

NOI.AC

1S 1024MB
统计

Z的家乡

时间限制 : 1 s

空间限制 : 1 gigabyte

题目

Z的家乡是一个美丽的地方。

经过历史的变迁,Z的家乡的地形演变成了一棵有$n$个节点的以1为根的树的形态,Z 感到很好奇,于是她查阅了历史资料,发现自己的家乡在演变过程中的种种美妙之处。

最开始的时候(很久很久以前),只有一个节点1.

在一些动荡的年代,这棵树就会发生巨大的变动,在第$i$次发生变动的时候,会有一个新的节点$i+1$出现,并且这个节点的父亲是$fa_{i+1}$。

每次变动之后,Z有一个初始为空的序列$P$,Z会调用DFS(1) 来得到一个序列$P$:

img

对于每一个节点$x$,Z可以任意选择遍历其儿子的顺序。

为了让得到的序列$P$尽量好看,Z会以一种让得到的序列$P$的字典序尽量大的方式进行遍历。

对于每一次变动,Z都希望知道这个字典序最大的$P$是什么,但是由于序列长度可能很长,所以请输出$f(P)$:

对于一个长度为$k$的序列$P$,定义$f(P)=\sum_{i=1}^kP_i\times 257933^{i-1}\mod 998244353$

输入

第一行一个整数$n$,表示树中节点的数量。

接下来一行$n-1$个数,对于其中第$i$个数$fa_{i+1}$表示第$i$次变动加入节点$i+1$,且节点$i+1$的父亲为$fa_{i+1}$。

输出

共$n-1$行,第$i$行表示第$i$次变动后能得到的字典序最大的序列$P$对应的$f(P)$.

样例输入&样例输出

见下发文件中的$hometown0$\sim$2.in$和$hometown0$\sim$2.ans$。

点此下载

数据范围

img