UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211854#3807. 随机游走x_add_b100926ms63684kbC++111.3kb2024-10-07 16:20:432024-10-29 10:32:45

answer

#include<bits/stdc++.h>

namespace IO
{
	template<typename Type>
	void read(Type &x){
		char ch=getchar();
		x=0;bool f=0;
		while(ch<'0'||ch>'9')
			f|=(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9')
			x=((x<<1)+(x<<3)+(ch^48)),ch=getchar();
		x=f?-x:x;
	}
}

using namespace std;

#define N 500005
#define LL long long

int n,w;
int val[N],fa[N];
LL sigmaV[N],sigmaW[N];
LL nowtime,ans;

bool opt1=true,opt2=true;

struct node
{
	int v,w;
	bool operator < (const node &a) const
	{
		return 1ll*sigmaW[v]*sigmaV[a.v]<1ll*sigmaW[a.v]*sigmaV[v];
	}
};

vector<node> Graph[N];

void dfs(int u)
{
	ans+=(1ll*nowtime*val[u]);
	for(int i=0;i<Graph[u].size();i++){
		nowtime+=Graph[u][i].w;
		dfs(Graph[u][i].v);
	}
}

void initdfs(int u)
{
	sigmaV[u]=val[u];
	for(int i=0;i<Graph[u].size();i++){
		int v=Graph[u][i].v,w=Graph[u][i].w;
		sigmaW[v]+=w;
		initdfs(v);
		sigmaV[u]+=sigmaV[v];
		sigmaW[u]+=sigmaW[v];
	}
}

int main()
{
//	freopen("ex_walk3.in","r",stdin);
	IO::read(n);
	for(int i=2;i<=n;i++){
		IO::read(fa[i]);IO::read(w);
		Graph[fa[i]].push_back({i,w});
	}	
	for(int i=1;i<=n;i++)
		IO::read(val[i]);
	initdfs(1);
	for(int i=1;i<=n;i++)
		sort(Graph[i].begin(),Graph[i].end());		
	dfs(1);
	printf("%lld",ans);
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 3ms
memory: 12936kb

input:

11
1 653
2 978
3 277
4 562
3 119
6 957
3 362
6 637
6 157
9 939
460 270 127 466 193 710 45 318 281 74...

output:

11506132

result:

ok single line: '11506132'

Test #2:

score: 10
Accepted
time: 19ms
memory: 15872kb

input:

50000
1 983
1 937
2 776
4 753
2 494
2 683
2 335
4 316
7 274
6 638
11 535
10 872
13 808
13 817
11 94
...

output:

276117269146880

result:

ok single line: '276117269146880'

Test #3:

score: 10
Accepted
time: 0ms
memory: 12972kb

input:

1000
1 729
1 239
1 433
1 445
1 877
1 648
1 284
1 814
1 287
1 941
1 183
1 126
1 65
1 500
1 823
1 725
...

output:

94592611925

result:

ok single line: '94592611925'

Test #4:

score: 10
Accepted
time: 0ms
memory: 12976kb

input:

1000
1 790
1 229
1 462
1 658
1 880
1 507
1 109
1 66
1 356
1 477
1 963
1 689
1 284
1 962
1 896
1 671
...

output:

91654782236

result:

ok single line: '91654782236'

Test #5:

score: 10
Accepted
time: 100ms
memory: 63684kb

input:

500000
1 87
2 160
3 87
4 518
5 214
6 654
7 329
8 614
9 590
10 13
11 546
12 35
13 417
14 304
15 884
1...

output:

31331837945244749

result:

ok single line: '31331837945244749'

Test #6:

score: 10
Accepted
time: 141ms
memory: 28480kb

input:

500000
1 697
1 11
1 698
1 189
1 824
1 524
1 163
1 335
1 959
1 690
1 368
1 168
1 673
1 398
1 918
1 42...

output:

16263658814895739

result:

ok single line: '16263658814895739'

Test #7:

score: 10
Accepted
time: 132ms
memory: 28480kb

input:

500000
1 148
1 159
1 990
1 585
1 837
1 364
1 754
1 576
1 756
1 426
1 502
1 201
1 185
1 251
1 17
1 20...

output:

16307730758229655

result:

ok single line: '16307730758229655'

Test #8:

score: 10
Accepted
time: 170ms
memory: 32092kb

input:

500000
1 252
1 377
1 130
4 779
5 531
4 815
2 176
4 514
9 21
9 142
2 72
11 293
11 579
9 870
7 731
9 3...

output:

48685536049668

result:

ok single line: '48685536049668'

Test #9:

score: 10
Accepted
time: 163ms
memory: 32108kb

input:

500000
1 484
1 48
3 523
2 793
4 822
1 622
3 874
4 54
6 568
4 867
11 500
7 974
4 966
7 793
1 140
1 40...

output:

49118321005585

result:

ok single line: '49118321005585'

Test #10:

score: 10
Accepted
time: 198ms
memory: 32112kb

input:

500000
1 456
2 231
2 525
4 823
2 377
1 72
2 644
5 391
1 984
1 996
7 590
4 604
7 359
3 138
4 843
3 22...

output:

21539113052010528

result:

ok single line: '21539113052010528'

Extra Test:

score: 0
Extra Test Passed