No.3343 Distance Sum of Large Tree
レベル :
/ AI推定難易度 : 1850
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 :
tassei903
/ テスター :
ponjuice
Nzt3
jupiter_68
noya2
タグ : / 解いたユーザー数 20
作問者 :
noya2
問題文最終更新日: 2025-11-13 15:56:53
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
You are given a sequence $(A_1, A_2, \dots, A_N)$ of length $N$ and sequences $(B_2, B_3, \dots, B_N), (C_2, C_3, \dots, C_N), (P_2, P_3, \dots, P_N)$ of length $N-1$.
Let $\displaystyle M = \sum_{1 \le i \le N} A_i$.
Define a tree $G(V, E)$ with $M$ vertices as follows.
- For $1 \le i \le N$, $1\le j \le A_i$, $(i, j) \in V$. We call this vertex the vertex $(i, j)$.
- For $1 \le i \le N$, $1\le j \lt A_i$, there is an edge connecting vertex $(i, j)$ and vertex $(i, j+1)$.
- For $2 \le i \le N$, there is an edge connecting vertex $(i, B_i)$ and vertex $(P_i, C_i)$.
- There are no other edges connecting vertices.
Here, the constraints guarantee that $G(V, E)$ is a tree.
Find the following value and print it modulo $998244353$.
$\displaystyle\sum_{u \in V}\sum_{v \in V} \text{dist}(u, v)$
Here, $\text{dist}(u, v)$ is the number of edges contained in the simple path whose endpoints are vertex $u$ and vertex $v$.
Constraints
- All inputs are integers.
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9 \space (1 \le i \le N)$
- $1 \le B_i \le A_i \space (2 \le i \le N)$
- $1 \le C_i \le A_{P_i} \space (2 \le i \le N)$
- $1 \le P_i \lt i \space (2 \le i \le N)$
Input
$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_2$ $B_3$ $\cdots$ $B_N$ $C_2$ $C_3$ $\cdots$ $C_N$ $P_2$ $P_3$ $\cdots$ $P_N$
Output
Print the answer.
Sample
Sample 1
Input
2 2 3 2 1 1
Output
36
The tree $G(V, E)$ given by the input is shown in the figure below.
Sample 2
Input
3 2 3 3 1 2 2 2 1 2
Output
140
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。