ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#173118 | #3152. Wandering on Tree | Alan_Zhaoyz | 100 | 9397ms | 131464kb | C++11 | 1.7kb | 2023-07-12 10:43:15 | 2023-07-12 13:05:13 |
answer
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=1e6+5,Mod=1e9+7;
int n,s,a[N],fa[N],deg[N];
vector<int> e[N];
ll inv[N],f[N],g[N][2][2],ans,prob[N][2];
void dfs(int u){
for(int v:e[u]) if(v!=fa[u]){
fa[v]=u,dfs(v);
if(u!=s) (f[u]+=(f[v]*inv[deg[u]-1]+inv[deg[v]]*inv[deg[u]])%Mod*inv[deg[u]])%=Mod;
}
}
void dfs2(int u){
ll cont=0;
if(!(deg[u]-(u!=s))){
For(i,0,1){
(cont+=g[u][i][1])%=Mod;
if(u!=s) (cont+=g[u][i][0]*inv[deg[u]]%Mod*inv[deg[fa[u]]-i+(fa[u]==s)])%=Mod;
}
}else if(deg[u]-(u!=s)==1){
int son=0;
for(int v:e[u]) if(v!=fa[u]) son=v;
For(i,0,1) (cont+=g[u][i][1]*f[son])%=Mod;
}
(ans+=cont*a[u])%=Mod;
ll sprob[2]{};
for(int v:e[u]) if(v!=fa[u]){
For(i,0,1){
prob[v][i]=(f[v]*inv[deg[u]-1-i+(u==s)]+inv[deg[v]]*inv[deg[u]-i+(u==s)])%Mod*inv[deg[u]-i+(u==s)]%Mod;
(sprob[i]+=prob[v][i])%=Mod;
}
}
for(int v:e[u]) if(v!=fa[u]){
For(i,0,1){
if(u!=s){
(g[v][1][1]+=g[u][i][0]*inv[deg[u]]%Mod*inv[deg[fa[u]]-i+(fa[u]==s)]%Mod*inv[deg[u]-1])%=Mod;
}
For(j,0,1){
(g[v][j][0]+=g[u][i][j]*inv[deg[u]-j+(u==s)])%=Mod;
(g[v][j][1]+=g[u][i][j]*(sprob[j]-prob[v][j]+Mod))%=Mod;
}
}
dfs2(v);
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
For(i,1,n) cin>>a[i];
For(i,1,n-1){
int u,v;
cin>>u>>v;
e[u].push_back(v),e[v].push_back(u);
}
For(i,1,n) deg[i]=e[i].size();
cin>>s;
inv[1]=1;
For(i,2,n) inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
dfs(s);
g[s][1][1]=1;
dfs2(s);
cout<<ans<<'\n';
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 24728kb
input:
8 759814385 318100469 539759949 963628324 281155634 697750042 935104062 476166261 3 7 7 4 3 2 2 6 6 ...
output:
130153227
result:
ok 1 number(s): "130153227"
Test #2:
score: 0
Accepted
time: 3ms
memory: 24728kb
input:
10 424726564 683278148 565392632 503696031 331194045 557568817 915499633 522648139 449300769 5087173...
output:
557326298
result:
ok 1 number(s): "557326298"
Test #3:
score: 0
Accepted
time: 4ms
memory: 24728kb
input:
9 593183218 602148746 726752891 355522583 782640810 863477908 452048838 238924512 852756239 5 7 5 4 ...
output:
57099086
result:
ok 1 number(s): "57099086"
Subtask #2:
score: 20
Accepted
Test #4:
score: 20
Accepted
time: 4ms
memory: 24760kb
input:
300 37041508 104990078 176284373 327103266 464374212 122045614 615291641 248099019 748109777 3372756...
output:
135249803
result:
ok 1 number(s): "135249803"
Test #5:
score: 0
Accepted
time: 4ms
memory: 24760kb
input:
294 758324800 685610349 907961456 661170815 898979208 98583521 32769816 578883323 964618693 98278366...
output:
141946388
result:
ok 1 number(s): "141946388"
Test #6:
score: 0
Accepted
time: 7ms
memory: 24760kb
input:
291 740985922 792303823 476880951 189564122 102450611 574481614 415484219 541502521 96617353 2339865...
output:
923059048
result:
ok 1 number(s): "923059048"
Test #7:
score: 0
Accepted
time: 0ms
memory: 24764kb
input:
284 344372808 978967203 412726006 677723991 123604207 692363797 940624452 204205155 915994211 894983...
output:
951781817
result:
ok 1 number(s): "951781817"
Test #8:
score: 0
Accepted
time: 4ms
memory: 24760kb
input:
291 794968340 471719742 732050684 222072803 357397261 220562934 951151790 203653444 949058577 220280...
output:
122214030
result:
ok 1 number(s): "122214030"
Test #9:
score: 0
Accepted
time: 4ms
memory: 24768kb
input:
294 301925331 94698297 957667963 642242475 891809663 522588544 738265292 655803987 53859258 59072033...
output:
676520534
result:
ok 1 number(s): "676520534"
Subtask #3:
score: 30
Accepted
Test #10:
score: 30
Accepted
time: 3ms
memory: 25044kb
input:
2967 96618965 970723748 788857367 627672408 449301391 13118385 39960168 654215538 618985166 38217488...
output:
926798032
result:
ok 1 number(s): "926798032"
Test #11:
score: 0
Accepted
time: 7ms
memory: 25036kb
input:
2980 82628010 876648723 937769687 922997982 485503765 560835050 567382186 672917821 751621435 544344...
output:
606507242
result:
ok 1 number(s): "606507242"
Test #12:
score: 0
Accepted
time: 7ms
memory: 25064kb
input:
2960 408236687 510750982 504790485 763613539 366794811 837336407 561994674 650690684 626366936 39605...
output:
571177571
result:
ok 1 number(s): "571177571"
Test #13:
score: 0
Accepted
time: 0ms
memory: 25052kb
input:
2960 506238889 807615518 666511272 703291946 446034490 884135684 753256324 600246683 320732402 24303...
output:
324928754
result:
ok 1 number(s): "324928754"
Test #14:
score: 0
Accepted
time: 7ms
memory: 25048kb
input:
2978 959722414 347159781 92089683 519743329 158525979 508863150 872146565 108528214 181229875 347250...
output:
320033134
result:
ok 1 number(s): "320033134"
Test #15:
score: 0
Accepted
time: 12ms
memory: 25052kb
input:
2919 370358609 778007887 520329662 289700509 827337586 99818328 971988402 104897047 519817725 330933...
output:
216021395
result:
ok 1 number(s): "216021395"
Test #16:
score: 0
Accepted
time: 9ms
memory: 25056kb
input:
2969 370754390 155133057 946983581 530457781 458892180 297076222 187137273 243826469 562113830 62123...
output:
24999395
result:
ok 1 number(s): "24999395"
Subtask #4:
score: 40
Accepted
Test #17:
score: 40
Accepted
time: 1317ms
memory: 130272kb
input:
990384 304034492 484150980 513641778 40284084 33326606 371604156 777646169 360418497 548849520 26234...
output:
651863294
result:
ok 1 number(s): "651863294"
Test #18:
score: 0
Accepted
time: 1098ms
memory: 129276kb
input:
991300 863233844 63478277 394820261 942038121 770261064 775352459 681948650 778396370 60674445 53356...
output:
815555364
result:
ok 1 number(s): "815555364"
Test #19:
score: 0
Accepted
time: 1344ms
memory: 130576kb
input:
993741 242961924 384447711 692265574 17073390 811783658 431799277 601451300 337448931 718711430 5567...
output:
737393355
result:
ok 1 number(s): "737393355"
Test #20:
score: 0
Accepted
time: 1348ms
memory: 131464kb
input:
998733 958843322 534311590 918437830 886760681 643885945 439741314 817505801 144092015 599609385 590...
output:
643678509
result:
ok 1 number(s): "643678509"
Test #21:
score: 0
Accepted
time: 1176ms
memory: 130800kb
input:
993618 45883005 748706214 718278410 204730942 555323574 776662260 146903494 907212627 360154258 8667...
output:
415818439
result:
ok 1 number(s): "415818439"
Test #22:
score: 0
Accepted
time: 1651ms
memory: 130312kb
input:
989197 898877983 550662507 220562804 727555553 843705410 483716586 391292374 298120137 141372801 160...
output:
837810977
result:
ok 1 number(s): "837810977"
Test #23:
score: 0
Accepted
time: 1388ms
memory: 131272kb
input:
997963 611456150 244490397 578081209 802707180 642699226 638381026 272062510 122037895 893002183 742...
output:
979542112
result:
ok 1 number(s): "979542112"
Extra Test:
score: 0
Extra Test Passed