AT_abc454_g [ABC454G] Mode in the Subtree

You are given a rooted tree with $ N $ vertices numbered $ 1 $ through $ N $ . Vertex $ 1 $ is the root, and the parent of vertex $ i $ is vertex $ p_i $ ( $ p_i \lt i $ ). Each vertex is colored: vertex $ i $ is colored with color $ c_i $ ( $ 1 \leq c_i \leq N $ ). For each $ v = 1, 2, \dots, N $ , solve the following problem: > Let $ f_i $ be the number of vertices colored with color $ i $ among the vertices in the subtree rooted at vertex $ v $ . > > Find: > > - the maximum value $ m $ among the values in the sequence $ (f_1, f_2, \dots, f_N) $ , and > - the number $ k $ of positive integers $ i $ not greater than $ N $ such that $ f_i = m $ .

The input is given from Standard Input in the following format: > $ N $ $ \mathrm{seed} $ $ M $ $ F $ $ q_2 $ $ q_3 $ $ \dots $ $ q_M $ $ d_1 $ $ d_2 $ $ \dots $ $ d_M $

Output $ \left(\displaystyle \sum_{i=1}^N (m_i \oplus i)\times (k_i \oplus i)\right) \bmod 998244353 $ .

### Input/Output Format The input and output for this problem follow a special format. #### Input Format From Standard Input, you are given the integer $ N $ along with integers $ \mathrm{seed}, M, F $ and $ q_2, q_3, \dots, q_M $ , $ d_1, d_2, \dots, d_M $ . Reconstruct $ p_2, p_3, \dots, p_N $ and $ c_1, c_2, \dots, c_N $ using the computation described by the following pseudocode. (Here, `2^31` means $ 2^{31}=2147483648 $ . Note that $ \mathrm{state} $ is a variable, and that a $ 64 $ -bit integer type is required for computing $ \mathrm{state} $ .) ``` state = seed for i=2 to N: if i