UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190013#3325. 跑路(run)Harry27182100271ms17660kbC++111.2kb2023-10-05 08:52:152023-10-05 12:34:47

answer

#include<bits/stdc++.h>
using namespace std;
struct edge{int v,nxt;}e[400005];
int h[200005],siz[200005],f[200005],g[200005],cnt,n,u,v,inv[200005];
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void dfs1(int u,int fa)
{
	siz[u]=0;f[u]=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs1(v,u);siz[u]++;
	}
	if(!siz[u]){f[u]=0;return;}
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		Add(f[u],1ll*inv[siz[u]]*f[v]%mod);
	}
}
void dfs2(int u,int fa)
{
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		int nowu=(1ll*(1ll*(g[u]-1+mod)*(siz[u]+(u!=1))%mod-f[v]+mod)*inv[siz[u]-(u==1)]%mod)%mod+(u!=1||siz[u]>=2);
		g[v]=(1ll*(nowu+1ll*(f[v]-1+mod)*siz[v]%mod)*inv[siz[v]+1]%mod+1)%mod;
		dfs2(v,u);
	}
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<n;i++)
    {
    	cin>>u>>v;
    	add(u,v);add(v,u);
	}
	dfs1(1,0);g[1]=f[1];dfs2(1,0);
	for(int i=1;i<=n;i++)cout<<g[i]<<'\n';
	return 0; 
}

详细

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

Test #1:

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

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: 1320kb

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: 1316kb

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: 1320kb

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: 1320kb

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: 44ms
memory: 17660kb

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: 56ms
memory: 10000kb

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: 59ms
memory: 9988kb

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: 57ms
memory: 9996kb

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: 55ms
memory: 9992kb

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