ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211851 | #3807. 随机游走 | LNY | 100 | 1284ms | 79304kb | C++ | 1.5kb | 2024-10-07 16:12:44 | 2024-10-29 10:32:40 |
answer
#include<bits/stdc++.h>
//A-随机游走
using namespace std;
typedef long long ll;
int res;
char ch;
int read()
{
res = 0, ch = getchar();
while (ch == ' ' || ch == '\n')
ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
int n;
int f, w;
struct Edge{
int ed, ti;
};
struct Tree{
int wi;
int wiSum, tiSum;
double im;//重要程度。= tiSum / wiSum
vector<Edge> ei;
}T[500005];
bool cmp(Edge xi, Edge yi)
{
return T[xi.ed].im < T[yi.ed].im;
}
void dfs(int rt)
{
//printf("#%d\n", rt);
for (int i = 0;i < T[rt].ei.size(); ++i)
T[T[rt].ei[i].ed].tiSum += T[rt].ei[i].ti,
dfs(T[rt].ei[i].ed),
T[rt].wiSum += T[T[rt].ei[i].ed].wiSum,
T[rt].tiSum += T[T[rt].ei[i].ed].tiSum;
T[rt].wiSum += T[rt].wi;
T[rt].im = (double)T[rt].tiSum / T[rt].wiSum;
sort(T[rt].ei.begin(), T[rt].ei.end(), cmp);
}
ll ans, tcnt;
void dfs_FindAns(int rt)
{
ans += T[rt].wi * tcnt;
//printf("#%d: %d, %lld\n", rt, T[rt].wi, tcnt);
for (int i = 0;i < T[rt].ei.size(); ++i)
tcnt += T[rt].ei[i].ti, dfs_FindAns(T[rt].ei[i].ed);
}
int main()
{
//freopen("ex_walk3.in", "r", stdin);
n = read();
for (int i = 2;i <= n; ++i)
f = read(), w = read(), T[f].ei.push_back({i, w});
for (int i = 1;i <= n; ++i)
T[i].wi = read();
dfs(1);
dfs_FindAns(1);
printf("%lld", ans);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 13ms
memory: 24640kb
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: 29ms
memory: 26840kb
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: 9ms
memory: 24660kb
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: 4ms
memory: 24660kb
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: 109ms
memory: 79304kb
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: 196ms
memory: 28644kb
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: 182ms
memory: 28640kb
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: 298ms
memory: 31956kb
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: 232ms
memory: 31968kb
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: 212ms
memory: 31972kb
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