UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190215#3325. 跑路(run)quliannanyishou100430ms35652kbC++111.4kb2023-10-05 11:47:552023-10-05 12:51:56

answer

#include<bits/stdc++.h>
using namespace std;
int m,a,b,l;
const int mod=998244353;
long long e[200010],inv[200010]={0,1},ans[200010],g[200010],temp,pre[200010],vis[200010];
vector <int> t[200010];
void dfs(int u,int fa)
{
	for(int i=0;i<t[u].size();++i)
	{
		if(fa==t[u][i])
		{
			continue;
		}
		dfs(t[u][i],u);
		l=t[u].size();
		if(u!=1)
		{
			l--;
		}
		e[u]+=(e[t[u][i]]+1)*inv[l]%mod;
		e[u]%=mod;
		if(vis[u]!=-1)
		{
			pre[t[u][i]]=pre[t[u][vis[u]]]+(e[t[u][vis[u]]]+1)*inv[t[u].size()-1]%mod;
			pre[t[u][i]]%=mod;
			//cout<<pre[t[u][i]]<<" "<<t[u][i]<<endl;
		}
		vis[u]=i;
	}
}
void dfs1(int u,int fa)
{
	long long suf=0;
	for(int i=t[u].size()-1;i>=0;--i)
	{
		if(fa==t[u][i])
		{
			continue;
		}
		l=t[t[u][i]].size();
		temp=(g[u]+1)*inv[t[u].size()-1]%mod+suf+pre[t[u][i]];
		temp%=mod;
		suf+=(e[t[u][i]]+1)*inv[t[u].size()-1]%mod;
		suf%=mod;
		g[t[u][i]]=temp;
		g[t[u][i]]%=mod;
		ans[t[u][i]]+=inv[l]*(temp+1)%mod;
		ans[t[u][i]]%=mod;
		dfs1(t[u][i],u);
		ans[u]+=(e[t[u][i]]+1)*inv[t[u].size()]%mod;
		ans[u]%=mod;
	}
} 
int main()
{
	cin>>m;
	for(int i=1;i<m;++i)
	{
		scanf("%d%d",&a,&b);
		t[a].push_back(b);
		t[b].push_back(a);
	}
	for(int i=2;i<=m;i++)
    {
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    memset(vis,-1,sizeof(vis));
	dfs(1,0);
	g[1]=-1;
	dfs1(1,0);
	ans[1]=e[1];
	for(int i=1;i<=m;++i)
	{
		printf("%lld\n",ans[i]);
	}
}

详细

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

Test #1:

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

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

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

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: 2ms
memory: 7628kb

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

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: 81ms
memory: 35652kb

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: 83ms
memory: 24472kb

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: 98ms
memory: 24456kb

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: 81ms
memory: 24464kb

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: 85ms
memory: 24464kb

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