ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190013 | #3325. 跑路(run) | Harry27182 | 100 | 271ms | 17660kb | C++11 | 1.2kb | 2023-10-05 08:52:15 | 2023-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