天才和疯子互相为邻

「ARC108F」Paint Tree

发表于 分类于

$Link$

给定一棵 $n$ 个点的树，每个点可以染成黑色或者白色。定义一种染色方案的得分为 $\operatorname{max}($ 最远的一对黑点的距离 $,$ 最远的一对白点的距离 $)$。

求所有可能的染色方案的得分之和，对 $10^9+7$ 取模。

$2\le n\le2\times10^5$。

套路性地，我们只需要容斥一下，改为求最远距离小于等于 $i$ 的方案数之和，其中 $i=[1,n]$，然后相减就可以求出最远距离等于 $i$ 的方案数。

我们设直径的两个端点为 $s$ 和 $t$，如果 $s,t$ 同色，那么最远距离显然就是直径的长度。

考虑 $s,t$ 异色的情况，由于我们只需要保证最远距离小于等于 $i$，答案简单了很多。对于一个点，如果它到 $s$ 和 $t$ 的距离都小于等于 $i$，这个点可以任意染色。如果都大于 $i$，则无解。剩下的情况它的颜色是确定的。

那我们直接开个桶，再做个前缀和，就可以知道对于 $i=[1,n]$，有多少个点可以任意染色了。

时间复杂度 $O(n)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 2e5;
const int mod = 1e9 + 7;

int n;
struct Edge {
    int to, next;
} edge[N * 2 + 1];
int start[N + 1], tot;
int pow2[N + 1];
int s, t, dis[N + 1], diss[N + 1], dist[N + 1];
int minn, buc[N + 1], ans;

inline void addedge(int u, int v)
{
    edge[++tot] = { v, start[u] };
    start[u] = tot;
    edge[++tot] = { u, start[v] };
    start[v] = tot;
    return;
}
inline int dfs(int u, int fa)
{
    int maxx = u;

    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa) {
            dis[v] = dis[u] + 1;
            int w = dfs(v, u);
            if (dis[w] > dis[maxx])
                maxx = w;
        }
    }
    return maxx;
}
int main()
{
    n = read();
    pow2[0] = 1;
    for (int i = 1; i <= n; i++)
        pow2[i] = 2ll * pow2[i - 1] % mod;
    for (int i = 1; i < n; i++)
        addedge(read(), read());
    s = dfs(1, 0);
    dis[s] = 0;
    t = dfs(s, 0);
    memcpy(diss, dis, 4 * (N + 1));
    dis[t] = 0;
    dfs(t, 0);
    memcpy(dist, dis, 4 * (N + 1));

    for (int i = 1; i <= n; i++) {
        minn = max(min(diss[i], dist[i]), minn);
        buc[max(diss[i], dist[i])]++;
    }
    for (int i = 1; i <= n; i++)
        buc[i] += buc[i - 1];
    for (int i = diss[t], la = 0; i >= 1; i--) {
        int w = (pow2[n] - 2ll * pow2[buc[i - 1]] % mod + mod) % mod;
        if (i <= minn)
            w = pow2[n];
        ans = (ans + 1ll * i * (w - la + mod)) % mod;
        la = w;
    }

    printf("%d\n", ans);
    return 0;
}