UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211851#3807. 随机游走LNY1001284ms79304kbC++1.5kb2024-10-07 16:12:442024-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;
}

Details

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

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