『XYGOI round1』一棵树

Luogu

IDLGP9437

Time1000ms

Memory512MB

DifficultyP4

动态规划 DPO2优化树形 DP洛谷月赛

于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。 MX 想知道这棵树所有路径的权值之和，即 $\sum\limits_{x=1}^n\sum\limits_{y=1}^nw(x,y)$ 为多少。答案可能很大，对 $998244353$ 取模。 ## Input 第一行一个正整数 $n$。第二行 $n$ 个非负整数 $a_i$。第三行 $n-1$ 个正整数，第 $i$ 个数 $p_i$ 表示节点 $p_i$ 与节点 $i+1$ 之间有边。保证 $1\le p_i\le i$。 ## Output 一行一个整数，表示答案。答案对 $998244353$ 取模。 [samples] ## Background java 今天带了一棵树到出题组，然后被不讲理的 MX 占为己有了。 ## Note ### 样例解释样例一解释：$1+12+123+2+21+23+3+32+321=538$。样例二解释：$5+521+5210+21+215+210+0+021+0215=6418$。 ### 数据范围 **本题采用捆绑测试。** 记 $V=\max\{a_i\}+1$。 |Subtask|分值|$n\le$|$V\le $|特殊性质| |:-:|:-:|:-:|:-:|:-:| |0|5|$1000$|$10$|| |1|15|$8000$|$10^9$|| |2|15|$10^6$|$10^9$|$p_i=i$| |3|15|$10^6$|$10^9$|$p_i=1$| |4|50|$10^6$|$10^9$|| 对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le a_i<10^9$。

Samples

Input #1

3
1 2 3
1 2

Output #1

Input #2

3
5 21 0
1 2

Output #2

Input #3

4
1 2 3 4
1 2 2

Output #3

Input #4

6
10 23 16 3 125 1
1 1 1 1 1

Output #4

API Response (JSON)

{
  "problem": {
    "name": "『XYGOI round1』一棵树",
    "description": {
      "content": "于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。 定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。 MX 想知道这棵树所有路径的权值之和，即 $\\sum\\limits_{x=1}^n\\sum",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9437"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。\n\n定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。\n\nMX 想知道这棵树所有路径的权值之和，即 $\\sum\\limits_{x=1}^n\\sum...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments