题目#

点分治进阶题目，状态很多，统计起来有点复杂。

分析#

首先肯定是点分治没得跑了，然后就是怎么计算的问题了。

我是先统计出来所有的 $mod$ 后的值，对于每一个节点的深度，可以计算出来这个点对三个剩余的贡献。

转移一下就好了。

因为去重的时候做了减法，所有答案可能是负值，要调整回来。

代码#

1
#include <bits/stdc++.h>
2
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
3
#define per(i, a, b) for(int i = (a); i >= (b); --i)
4
#define debug(x) cerr << #x << ' ' << x << endl;
5
#define size sizeeeeeeee
6
using namespace std;
7

8
typedef long long ll;
9
const int MOD = 1e9+7;
10
const int MAXN = 1e4 + 7;
11

12
ll ans1, ans2, ans3, cnt[4];
13
int n, root, size, tot = 0;
14
int son[MAXN], f[MAXN], head[MAXN];
15
int dep[MAXN]; bool vis[MAXN];
16
struct node{
17
    int u, w, nxt;
18
}; vector<node> E;
19
void add(int u, int v, int w) {
20
    E.push_back(node{v, w, head[u]});
21
    head[u] = tot++;
22
}
23
void get_rt(int x, int fa = 0) {
24
    son[x] = 1; f[x] = 0;
25
    for(int j = head[x]; ~j; j = E[j].nxt) {
26
        int u = E[j].u, w = E[j].w;
27
        if(vis[u] || u == fa)   continue;
28
        get_rt(u, x);
29
        son[x] += son[u];
30
        f[x] = max(f[x], son[u]);
31
    }
32
    f[x] = max(f[x], size - son[x]);
33
    if(f[x] < f[root]) root = x;
34
}
35
vector<int> v;
36
void get_dep(int x, int fa) {
37
    v.push_back(dep[x]); cnt[dep[x]%3]++;
38
    for(int j = head[x]; ~j; j = E[j].nxt) {
39
        int u = E[j].u, w = E[j].w;
40
        if(vis[u] || u == fa)   continue;
41
        dep[u] = dep[x] + w;
42
        get_dep(u, x);
43
    }
44
}
45
void calc(int x, int op) {
46
    memset(cnt, 0, sizeof cnt); v.clear();
47
    get_dep(x, 0);
48
    ll res0, res1, res2;
49
    res0 = res1 = res2 = 0;
50
    for(int p: v) {
51
        int offset = p%3;
52
        if(offset == 0) {
53
            res0 += op * (cnt[0] - 1) * p;
54
            res1 += op * cnt[1] * p;
55
            res2 += op * cnt[2] * p;
56
        } else if(offset == 1) {
57
            res0 += op * cnt[2] * p;
58
            res1 += op * cnt[0] * p;
59
            res2 += op * (cnt[1] - 1) * p;
60
        } else {
61
            res0 += op * cnt[1] * p;
62
            res1 += op * (cnt[2] - 1) * p;
63
            res2 += op * cnt[0] * p;
64
        }
65
        res0 %= MOD; res1 %= MOD; res2 %= MOD;
66
    }
67
    ans1 += res0; ans2 += res1; ans3 += res2;
68
    ans1 %= MOD; ans2 %= MOD; ans3 %= MOD;
69
}
70
void solve(int x) {
71
    dep[x] = 0; calc(x, 1); vis[x] = 1;
72
    for(int j = head[x]; ~j; j = E[j].nxt) {
73
        int u = E[j].u, w = E[j].w;
74
        if(vis[u])  continue;
75
        dep[u] = w; calc(u, -1);
76
        root = 0; size = son[u];
77
        get_rt(u);
78
        solve(root);
79
    }
80
}
81
int main(int argc, char const *argv[])
82
{
83
    while(~scanf("%d", &n)) {
84
        memset(head, -1, sizeof head);
85
        memset(vis, 0, sizeof vis);
86
        E.clear(); tot = 0;
87
        int u, v, w;
88
        rep(i, 1, n-1) {
89
            scanf("%d %d %d", &u, &v, &w);
90
            u++; v++;
91
            add(u, v, w); add(v, u, w);
92
        }
93
        root = 0; f[0] = size = n;
94
        get_rt(1, 0);
95
        ans1 = ans2 = ans3 = 0;
96
        solve(root);
97
        ans1 = ans1 * 2 % MOD;
98
        ans2 = ans2 * 2 % MOD;
99
        ans3 = ans3 * 2 % MOD;
100
        ans1 = (ans1 + MOD) % MOD;
101
        ans2 = (ans2 + MOD) % MOD;
102
        ans3 = (ans3 + MOD) % MOD;
103
        printf("%lld %lld %lld\n", ans1, ans2, ans3);
104
    }
105
    return 0;
106
}