UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#173118#3152. Wandering on TreeAlan_Zhaoyz1009397ms131464kbC++111.7kb2023-07-12 10:43:152023-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