P9437 『XYGOI round1』一棵树

题目背景

java 今天带了一棵树到出题组，然后被不讲理的 MX 占为己有了。

题目描述

于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。

定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。

MX 想知道这棵树所有路径的权值之和，即 $\sum _{x=1}^n\sum _{y=1}^{n}w(x,y)$ 为多少。

答案可能很大，对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个非负整数 $a_i$。

第三行 $n-1$ 个正整数，第 $i$ 个数 $p_i$ 表示节点 $p_i$ 与节点 $i+1$ 之间有边。保证 $1\le p_i\le i$。

输出格式

一行一个整数，表示答案。答案对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3
1 2 3
1 2

输出 #1

538

输入输出样例 #2

输入 #2

3
5 21 0
1 2

输出 #2

6418

输入输出样例 #3

输入 #3

4
1 2 3 4
1 2 2

输出 #3

1900

输入输出样例 #4

输入 #4

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

输出 #4

7680868

说明/提示

样例解释

样例一解释：$1+12+123+2+21+23+3+32+321=538$。

样例二解释：$5+521+5210+21+215+210+0+021+0215=6418$。

数据范围

本题采用捆绑测试。

记 V=max⁡{ai}+1V=\max\{a_i\}+1V=max{ai​}+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$。

C++实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=998244353;
ll n,a[N],f[N],g[N],siz[N],sum[N],ans;
vector<int>adj[N];
ll get(ll x){
	if(x==0)return 10;
	ll res=1;
	while(x){res*=10;x/=10;}
	return res;
}
void dfs(int u,int lst){
	siz[u]=1;
	ll t=get(a[u]);f[u]=a[u];
	for(int i=0;i<adj[u].size();++i){
		int v=adj[u][i];if(v==lst)continue;
		dfs(v,u);siz[u]+=siz[v];f[u]=(f[u]+f[v]*t+siz[v]*a[u])%mod;sum[u]=(sum[u]+f[v])%mod;
	}
}
void dfs2(int u,int lst){
	ll tu=get(a[u]);
	for(int i=0;i<adj[u].size();++i){
		ll v=adj[u][i],tv=get(a[v]);if(v==lst)continue;
		g[v]=(g[u]+(sum[u]-f[v]+mod)%mod)%mod*tu+(n-siz[v])*a[u];g[v]%=mod;
		ans=(ans+(g[v]+sum[v])*tv+n*a[v])%mod;
		dfs2(v,u);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;for(int i=1;i<=n;++i)cin>>a[i];
	for(int u=2;u<=n;++u){
		int v;cin>>v;
		adj[u].push_back(v);adj[v].push_back(u);
	}
	dfs(1,0);ans+=f[1];dfs2(1,0);
	cout<<ans<<endl;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容