UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214265#2763. 幻想乡的拜访nodgd1001476ms32828kbC++1.0kb2024-11-16 21:24:182024-11-16 23:13:33

answer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000 + 5;
const int P = 1000000007;

int N;
int elast[MAX_N], ey[MAX_N << 1], enext[MAX_N << 1];
long long siz[MAX_N], now, ans;

void dfs1(int u, int fa) {
    siz[u] = u;
    for (int j = elast[u], v; j; j = enext[j]) {
        if ((v = ey[j]) != fa) {
            dfs1(v, u);
            siz[u] += siz[v];
        }
    }
    now += siz[u];
}
void dfs2(int u, int fa) {
    now += siz[1] - siz[u] * 2;
    ans = (ans + now % P * u) % P;
    for (int j = elast[u], v; j; j = enext[j]) {
        if ((v = ey[j]) != fa) {
            dfs2(v, u);
        }
    }
    now -= siz[1] - siz[u] * 2;
}

int main() {
    scanf("%d", &N);
    for (int i = 1, j = 1; i < N; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        ey[j] = y, enext[j] = elast[x], elast[x] = j ++;
        ey[j] = x, enext[j] = elast[y], elast[y] = j ++;
    }
    dfs1(1, 0);
    dfs2(1, 0);
    ans = ans & 1 ? ans + P >> 1 : ans >> 1;
    printf("%lld\n", ans);
    return 0;
}

Details

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

Test #1:

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

input:

200
20 160
90 160
5 90
78 90
186 90
149 90
104 78
136 160
106 78
100 106
168 90
30 5
85 136
28 149
1...

output:

104425891

result:

ok single line: '104425891'

Test #2:

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

input:

200
49 91
20 91
147 91
131 20
36 131
9 131
51 147
173 51
32 36
169 51
180 51
2 91
133 2
72 20
14 169...

output:

145567217

result:

ok single line: '145567217'

Test #3:

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

input:

200
44 72
187 72
115 72
124 115
80 124
34 72
22 115
162 34
123 44
93 22
135 80
5 124
112 72
76 187
3...

output:

226420652

result:

ok single line: '226420652'

Test #4:

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

input:

3000
940 1649
220 1649
1438 1649
2264 1649
1467 940
1825 220
1646 940
571 220
1419 220
2509 1438
264...

output:

781596579

result:

ok single line: '781596579'

Test #5:

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

input:

3000
2156 216
2422 2156
2801 216
2504 2156
2701 2156
2582 2801
1558 2156
864 2582
737 864
2919 1558
...

output:

236427659

result:

ok single line: '236427659'

Test #6:

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

input:

3000
2966 2885
2657 2885
2613 2966
1686 2613
2803 2885
191 2657
2824 2657
675 2657
2693 191
2798 191...

output:

688220644

result:

ok single line: '688220644'

Test #7:

score: 10
Accepted
time: 466ms
memory: 32812kb

input:

1000000
984750 990109
970095 984750
996126 970095
998081 990109
987074 970095
962711 970095
916630 9...

output:

192557796

result:

ok single line: '192557796'

Test #8:

score: 10
Accepted
time: 325ms
memory: 32692kb

input:

1000000
947305 936749
948062 947305
970449 947305
988744 948062
998703 988744
986194 947305
997762 9...

output:

160385007

result:

ok single line: '160385007'

Test #9:

score: 10
Accepted
time: 399ms
memory: 32828kb

input:

1000000
952012 962256
982471 962256
955412 952012
953636 962256
991390 952012
998704 953636
999294 9...

output:

308556344

result:

ok single line: '308556344'

Test #10:

score: 10
Accepted
time: 286ms
memory: 32792kb

input:

1000000
900864 972452
986047 900864
953966 972452
977801 986047
997024 972452
954755 953966
999240 9...

output:

201471911

result:

ok single line: '201471911'