UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214270#2763. 幻想乡的拜访ThySecret600ms2892kbC++112.6kb2024-11-16 21:57:502024-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;
}

Details

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

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...

output:


result: