ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190025 | #3325. 跑路(run) | gaojieming | 100 | 760ms | 16820kb | C++11 | 1.7kb | 2023-10-05 08:59:49 | 2023-10-05 12:36:04 |
answer
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pn putchar('\n')
#define maxint 2147483647
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define maxn 200005
#define int ll
#define mod 998244353
using namespace std;
struct Gragh
{
int v,nex;
}e[maxn<<1];
int n,top;
int c[maxn],f[maxn],cd[maxn];
il void build_gra(int u,int v)
{
e[++top]=(Gragh){v,c[u]},c[u]=top;
}
il int ksm(int x,int y)
{
int ret=1;
while(y)
{
if(y&1)ret=ret*x%mod;
x=x*x%mod,y>>=1;
}
return ret;
}
il void upd(int &x,int y)
{
x+=y;
while(x>=mod)x-=mod;
while(x<0)x+=mod;
}
il void dfs(int pos,int fa=0)
{
if(!c[pos])
{
f[pos]=1;
return;
}
for(int i=c[pos];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa)continue;
cd[pos]++;
dfs(v,pos);
upd(f[pos],f[v]+1);
}
f[pos]=f[pos]*ksm(cd[pos],mod-2)%mod;
}
il void rdfs(int pos,int fa=0)
{
for(int i=c[pos];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa)continue;
int tmp=f[pos]*cd[pos];
upd(tmp,-f[v]-1);
tmp=tmp*ksm(cd[pos]-1,mod-2)%mod;
f[v]=f[v]*cd[v]%mod;
upd(f[v],tmp+1);
cd[v]++;
f[v]=f[v]*ksm(cd[v],mod-2)%mod;
rdfs(v,pos);
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
scanf("%lld",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
build_gra(u,v),build_gra(v,u);
}
dfs(1);
rdfs(1);
for(int i=1;i<=n;i++)
printf("%lld\n",f[i]);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1284kb
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: 1268kb
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: 1260kb
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: 1268kb
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: 1264kb
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: 149ms
memory: 16820kb
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: 161ms
memory: 12988kb
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: 144ms
memory: 12980kb
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: 152ms
memory: 12988kb
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: 154ms
memory: 12984kb
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