UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190038#3325. 跑路(run)ddh123100687ms26196kbC++111.1kb2023-10-05 09:13:032023-10-05 12:37:00

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
int qp(int a,int b){
	if(!b)return 1;
	if(b&1)return qp(a,b-1)*a%mod;
	int t=qp(a,b>>1);
	return t*t%mod;
}
int n,u,v,dp[200005],inv[200005],cnt[200005];
vector<int>E[200005];
void dfs1(int p,int fa=0){
	for(auto &&v:E[p])
		if(v!=fa){
			dfs1(v,p);
			dp[p]=(dp[p]+dp[v])%mod,cnt[p]++;
		}
	dp[p]=(dp[p]*inv[cnt[p]]%mod+1)%mod;
}
void dfs2(int p,int fa=0){
	int idx=0,sum;
	for(auto v:E[p])
		if(v!=fa){
			sum=(((dp[p]-1+mod)%mod*(cnt[p]+(p>1))%mod-dp[v]+mod)%mod*inv[cnt[p]-(p==1)]+1)%mod;
			dp[v]=(((dp[v]-1+mod)%mod*cnt[v]%mod+sum)*inv[cnt[v]+1]%mod+1)%mod;
			dfs2(v,p),idx++;
		}
}
signed main(){
	n=read(),inv[0]=1;
	for(int i=1;i<=n;i++)inv[i]=qp(i,mod-2);
	for(int i=1;i<n;i++){
		u=read(),v=read();
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs1(1),dfs2(1);
	for(int i=1;i<=n;i++)printf("%lld\n",(dp[i]+mod-1)%mod);
	return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 4ms
memory: 5992kb

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

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

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

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

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: 131ms
memory: 26196kb

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: 132ms
memory: 19432kb

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: 155ms
memory: 19432kb

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: 126ms
memory: 19432kb

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: 139ms
memory: 19432kb

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