ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190215 | #3325. 跑路(run) | quliannanyishou | 100 | 430ms | 35652kb | C++11 | 1.4kb | 2023-10-05 11:47:55 | 2023-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