打卡信奥刷题（3343）用C++实现信奥题 P9437 『XYGOI round1』一棵树

P9437 『XYGOI round1』一棵树

题目背景

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

题目描述

于是 MX 有一棵

n

n

n 个节点的树，每个点上有一个数字

a

i

a_i

ai​。

定义一条路径

(

x

,

y

)

(x,y)

(x,y) 的权值

w

(

x

,

y

)

w(x,y)

w(x,y) 为，从

x

x

x 走到

y

y

y 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字

3

,

21

,

0

,

5

3,21,0,5

3,21,0,5 的四个节点，那么这个路径的权值为

32105

32105

32105。

MX 想知道这棵树所有路径的权值之和，即

∑

x

=

1

n

∑

y

=

1

n

w

(

x

,

y

)

\\sum\\limits_{x=1}^n\\sum\\limits_{y=1}^nw(x,y)

x=1∑n​y=1∑n​w(x,y) 为多少。

答案可能很大，对

998244353

998244353

998244353 取模。

输入格式

第一行一个正整数

n

n

n。

第二行

n

n

n 个非负整数

a

i

a_i

ai​。

第三行

n

−

1

n-1

n−1 个正整数，第

i

i

i 个数

p

i

p_i

pi​ 表示节点

p

i

p_i

pi​ 与节点

i

+

1

i+1

i+1 之间有边。保证

1

≤

p

i

≤

i

1\\le p_i\\le i

1≤pi​≤i。

输出格式

一行一个整数，表示答案。答案对

998244353

998244353

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

1+12+123+2+21+23+3+32+321=538

1+12+123+2+21+23+3+32+321=538。

样例二解释：

5

+

521

+

5210

+

21

+

215

+

210

+

0

+

021

+

0215

=

6418

5+521+5210+21+215+210+0+021+0215=6418

5+521+5210+21+215+210+0+021+0215=6418。

数据范围

本题采用捆绑测试。

记

V

=

max

⁡

{

a

i

}

+

1

V=\\max\\{a_i\\}+1

V=max{ai​}+1。

对于

100

%

100\\%

100% 的数据，

1

≤

n

≤

10

6

1\\le n\\le 10^6

1≤n≤106，

0

≤

a

i

<

10

9

0\\le a_i<10^9

0≤ai​<109。

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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容