ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214265 | #2763. 幻想乡的拜访 | nodgd | 100 | 1476ms | 32828kb | C++ | 1.0kb | 2024-11-16 21:24:18 | 2024-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'