ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190038 | #3325. 跑路(run) | ddh123 | 100 | 687ms | 26196kb | C++11 | 1.1kb | 2023-10-05 09:13:03 | 2023-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