UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185709#3332. 化圆为方Crayon_ptwk1005676ms385736kbC++994b2023-09-30 10:13:532023-09-30 12:43:10

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
#define ll long long
const long long mod = 998244353;
int n;
ll sz[N],ans;
vector<int> g[N];
char ch;
inline int read(){
    int res=0;
    ch=getchar();
    while(!(ch>='0'&&ch<='9'))  ch=getchar();
    while((ch>='0'&&ch<='9'))
        res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
    return res;
}
inline ll kpow(ll a,ll b){
    ll base=a,ret=1;
    while(b){
        if(b&1) ret=ret*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ret%mod;
}
void dfs(int u,int dep){
    if(g[u].size()==0){
        sz[u]=1;
        ans+=kpow(sz[u],mod-2);
        return ;
    }
    for(int i=0;i<g[u].size();++i){
        dfs(g[u][i],dep+1);
        sz[u]+=sz[g[u][i]];
    }
    sz[u]++;
    ans+=kpow(sz[u],mod-2);
    ans%=mod;
}
int main(){
    cin>>n;
    for(int i=2,x;i<=n;++i)
        x=read(),g[x].push_back(i);
    dfs(1,1);
    cout<<ans<<endl;
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 53ms
memory: 235620kb

input:

10
1 1 3 1 4 6 6 7 8

output:

922187646

result:

ok 1 number(s): "922187646"

Test #2:

score: 10
Accepted
time: 29ms
memory: 235624kb

input:

10
1 2 3 2 3 2 2 4 9

output:

177465669

result:

ok 1 number(s): "177465669"

Test #3:

score: 10
Accepted
time: 48ms
memory: 235628kb

input:

10
1 1 1 1 3 4 6 7 7

output:

216286283

result:

ok 1 number(s): "216286283"

Test #4:

score: 10
Accepted
time: 189ms
memory: 250552kb

input:

999984
1 2 3 3 2 1 1 1 9 10 8 7 13 12 3 14 11 3 18 12 9 5 18 21 13 24 4 8 24 22 2 11 8 10 1 7 30 11 ...

output:

215590743

result:

ok 1 number(s): "215590743"

Test #5:

score: 10
Accepted
time: 208ms
memory: 250568kb

input:

999945
1 2 2 2 1 4 5 7 6 6 11 1 13 5 4 14 17 3 8 13 9 9 10 7 21 15 26 4 27 8 21 21 13 10 22 1 2 17 1...

output:

455596765

result:

ok 1 number(s): "455596765"

Test #6:

score: 10
Accepted
time: 192ms
memory: 250560kb

input:

999979
1 2 1 4 3 2 3 7 3 2 10 6 6 6 7 16 8 17 15 6 1 17 2 18 5 26 5 21 3 2 2 13 2 10 33 17 27 3 38 1...

output:

152327247

result:

ok 1 number(s): "152327247"

Test #7:

score: 10
Accepted
time: 196ms
memory: 250492kb

input:

999988
1 2 1 3 2 2 2 8 9 4 8 9 5 13 11 3 4 1 2 8 15 19 10 1 12 17 17 9 23 6 5 25 15 2 4 21 8 2 2 21 ...

output:

372616342

result:

ok 1 number(s): "372616342"

Test #8:

score: 10
Accepted
time: 1582ms
memory: 385716kb

input:

9999321
1 1 3 4 3 3 7 1 3 7 1 11 9 12 3 3 9 14 7 13 10 19 22 19 22 26 17 24 8 4 9 32 4 29 10 27 20 1...

output:

735203174

result:

ok 1 number(s): "735203174"

Test #9:

score: 10
Accepted
time: 1557ms
memory: 385736kb

input:

9999983
1 2 2 1 4 3 3 8 1 9 8 4 1 11 11 1 17 14 17 10 4 1 11 2 24 17 12 19 14 20 26 30 9 14 27 15 36...

output:

195679217

result:

ok 1 number(s): "195679217"

Test #10:

score: 10
Accepted
time: 1622ms
memory: 385688kb

input:

9999974
1 2 1 1 4 1 4 2 5 10 5 11 12 5 10 4 12 12 13 12 8 12 8 1 20 17 22 13 17 24 3 14 24 11 8 6 10...

output:

950738359

result:

ok 1 number(s): "950738359"