UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190025#3325. 跑路(run)gaojieming100760ms16820kbC++111.7kb2023-10-05 08:59:492023-10-05 12:36:04

answer

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pn putchar('\n')
#define maxint 2147483647
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define maxn 200005
#define int ll
#define mod 998244353
using namespace std;
struct Gragh
{
    int v,nex;
}e[maxn<<1];
int n,top;
int c[maxn],f[maxn],cd[maxn];
il void build_gra(int u,int v)
{
    e[++top]=(Gragh){v,c[u]},c[u]=top;
}
il int ksm(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=ret*x%mod;
        x=x*x%mod,y>>=1;
    }
    return ret;
}
il void upd(int &x,int y)
{
    x+=y;
    while(x>=mod)x-=mod;
    while(x<0)x+=mod;
}
il void dfs(int pos,int fa=0)
{
    if(!c[pos])
    {
        f[pos]=1;
        return;
    }
    for(int i=c[pos];i;i=e[i].nex)
    {
        int v=e[i].v;
        if(v==fa)continue;
        cd[pos]++;
        dfs(v,pos);
        upd(f[pos],f[v]+1);
    }
    f[pos]=f[pos]*ksm(cd[pos],mod-2)%mod;
}
il void rdfs(int pos,int fa=0)
{
    for(int i=c[pos];i;i=e[i].nex)
    {
        int v=e[i].v;
        if(v==fa)continue;
        int tmp=f[pos]*cd[pos];
        upd(tmp,-f[v]-1);
        tmp=tmp*ksm(cd[pos]-1,mod-2)%mod;
        f[v]=f[v]*cd[v]%mod;
        upd(f[v],tmp+1);
        cd[v]++;
        f[v]=f[v]*ksm(cd[v],mod-2)%mod;
        rdfs(v,pos);
    }
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    scanf("%lld",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        build_gra(u,v),build_gra(v,u);
    }
    dfs(1);
    rdfs(1);
    for(int i=1;i<=n;i++)
        printf("%lld\n",f[i]);
    return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 0ms
memory: 1284kb

input:

1000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 2...

output:

999
499122676
499122676
499122676
499122676
499122676
499122676
499122676
499122676
499122676
499122...

result:

ok 1000 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 1268kb

input:

1000
1 2
1 3
2 4
2 5
2 6
2 7
6 8
2 9
4 10
10 11
2 12
7 13
4 14
10 15
12 16
13 17
13 18
15 19
13 20
2...

output:

105370038
751059694
210740076
6468493
377114134
105370038
937240333
210740076
377114134
19869236
528...

result:

ok 1000 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 1260kb

input:

1000
1 2
2 3
1 4
2 5
1 6
3 7
1 8
6 9
5 10
10 11
9 12
8 13
7 14
5 15
15 16
11 17
15 18
14 19
12 20
12...

output:

578381519
340245486
754306293
105679124
586057892
241705711
754306293
385587680
241705711
189982332
...

result:

ok 1000 lines

Test #4:

score: 10
Accepted
time: 0ms
memory: 1268kb

input:

1000
1 2
2 3
2 4
4 5
3 6
6 7
4 8
5 9
4 10
5 11
7 12
5 13
5 14
8 15
13 16
10 17
10 18
14 19
17 20
19 ...

output:

760833538
839970476
629977858
517347582
723817525
629977858
629977858
12150271
904771907
63558202
90...

result:

ok 1000 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 1264kb

input:

1000
1 2
2 3
3 4
2 5
3 6
3 7
1 8
7 9
7 10
6 11
10 12
5 13
5 14
7 15
9 16
9 17
10 18
16 19
12 20
16 2...

output:

147781659
529790329
942467149
258378513
431269224
961059551
331790560
295563318
706953014
879864477
...

result:

ok 1000 lines

Test #6:

score: 10
Accepted
time: 149ms
memory: 16820kb

input:

200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19...

output:

199999
499222176
499222176
499222176
499222176
499222176
499222176
499222176
499222176
499222176
499...

result:

ok 200000 lines

Test #7:

score: 10
Accepted
time: 161ms
memory: 12988kb

input:

200000
1 2
1 3
3 4
3 5
3 6
6 7
6 8
4 9
9 10
10 11
8 12
5 13
4 14
10 15
9 16
11 17
17 18
14 19
14 20
...

output:

892174245
786104137
839139190
629421934
892174245
539324811
808987217
654054697
343786540
562792532
...

result:

ok 200000 lines

Test #8:

score: 10
Accepted
time: 144ms
memory: 12980kb

input:

200000
1 2
2 3
2 4
3 5
2 6
1 7
2 8
4 9
2 10
8 11
2 12
8 13
8 14
12 15
7 16
16 17
11 18
14 19
10 20
1...

output:

976656165
818629691
227972899
227972899
455945798
622319856
976656165
679170087
455945798
144785870
...

result:

ok 200000 lines

Test #9:

score: 10
Accepted
time: 152ms
memory: 12988kb

input:

200000
1 2
2 3
1 4
4 5
5 6
4 7
5 8
3 9
5 10
6 11
3 12
5 13
5 14
9 15
12 16
15 17
13 18
13 19
19 20
2...

output:

881588557
881588557
88603529
676329231
401424116
440503341
16249494
481708940
565574824
481708940
88...

result:

ok 200000 lines

Test #10:

score: 10
Accepted
time: 154ms
memory: 12984kb

input:

200000
1 2
2 3
3 4
4 5
2 6
4 7
5 8
7 9
7 10
10 11
11 12
4 13
7 14
9 15
10 16
15 17
17 18
11 19
10 20...

output:

488015892
990840163
488015891
732023835
155267773
488015892
698704971
310535546
964925492
931496495
...

result:

ok 200000 lines

Extra Test:

score: 0
Extra Test Passed