ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214270 | #2763. 幻想乡的拜访 | ThySecret | 60 | 0ms | 2892kb | C++11 | 2.6kb | 2024-11-16 21:57:50 | 2024-11-16 23:13:50 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);
typedef long long LL;
typedef pair<int, int> PII;
const int N = 200010;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
template<typename Type>
inline void read(Type &res)
{
res = 0;
int ch = getchar(), flag = 0;
while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }
int n, ans, cur;
int h[N], e[N << 1], ne[N << 1], idx;
int sz[N], depth[N];
inline void add(int a, int b) { e[++ idx] = b, ne[idx] = h[a], h[a] = idx; }
// void dfs(int ver, int pre)
// {
// sz[ver] = ver, sum[ver] = 0;
// for (int i = h[ver]; ~i; i = ne[i])
// {
// int to = e[i];
// if (to == pre) continue;
// dfs(to, ver);
// f[ver] = (f[ver] + sz[to] * sum[ver] % mod + sz[ver] * (sum[to] + sz[to]) % mod) % mod;
// sum[ver] = (sum[ver] + sum[to] + sz[to]) % mod;
// sz[ver] += sz[to];
// }
// // f[ver] = (f[ver] + ver * sum[ver]) % mod;
// }
void dfs(int ver, int pre)
{
sz[ver] = ver, depth[ver] = depth[pre] + 1;
for (int i = h[ver]; ~i; i = ne[i])
{
int to = e[i];
if (to == pre) continue;
dfs(to, ver);
sz[ver] += sz[to];
}
}
void dfs2(int ver, int pre)
{
for (int i = h[ver]; ~i; i = ne[i])
{
int to = e[i];
if (to == pre) continue;
int rest = n * (n + 1) / 2 - 2 * sz[to];
cur = (cur + rest) % mod;
ans = (ans + cur * to % mod) % mod;
dfs2(to, ver);
cur = (cur - rest + mod) % mod;
}
}
signed main()
{
memset(h, -1, sizeof h), idx = -1;
read(n);
for (int i = 1; i < n; i ++)
{
int a, b; read(a, b);
add(a, b), add(b, a);
}
depth[0] = -1;
dfs(1, 0);
for (int ver = 1; ver <= n; ver ++) ans += ver * depth[ver];
cur = ans;
dfs2(1, 0);
// cout << ans / 2 << '\n';
cout << ans * 500000004 % mod << '\n';
// cout << f[1] << '\n';
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 2748kb
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: 2752kb
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: 2748kb
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: 2888kb
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: 2892kb
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: 2880kb
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: 0
Runtime Error
input:
1000000 984750 990109 970095 984750 996126 970095 998081 990109 987074 970095 962711 970095 916630 9...
output:
result:
Test #8:
score: 0
Runtime Error
input:
1000000 947305 936749 948062 947305 970449 947305 988744 948062 998703 988744 986194 947305 997762 9...
output:
result:
Test #9:
score: 0
Runtime Error
input:
1000000 952012 962256 982471 962256 955412 952012 953636 962256 991390 952012 998704 953636 999294 9...
output:
result:
Test #10:
score: 0
Runtime Error
input:
1000000 900864 972452 986047 900864 953966 972452 977801 986047 997024 972452 954755 953966 999240 9...