天才和疯子互相为邻

「CF516D」Drazil and Morning Exercise

发表于 分类于

$Link$

给你一棵 $n$ 个点的树，定义每个点的权值为其到最远的叶子节点的距离 $dis$。

$q$ 次询问，每次询问给你一个 $l$，问最多能选出多少个点，使得 $dis_{max}-dis_{min}\le l$，且这些点联通。

$1\le n\le10^5,1\le q\le50$。

首先显然是两遍 $dfs$ 算出每个点的 $dis$。

考虑把 $dis$ 最小的点作为根，这样我们有一个很好的性质，其中 $v\in u$ 表示 $v$ 在 $u$ 的子树内。
$$
\forall v\in u,dis_v\ge dis_u
$$
如何证明？

稍加思考可以知道，离某个点最远的叶子结点的集合，必定包含直径的两个端点之一，而 $dis$ 最小的点，正是直径的中点，于是显然成立。

那么，直接按 $dis$ 从大到小枚举所选的点中的最小的，用并查集维护联通性，每次删去不满足条件的点。由于删去的点必定是离这个点最远的，因此不会影响联通性。时间复杂度 $O(n+qn\alpha)$。

$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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
inline ll read()
{
    ll 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 = 1e5;

int n, q;
ll l;
struct Edge {
    int to, next, w;
} edge[(N << 1) + 1];
int start[N + 1], d[N + 1], tot;
ll dis[N + 1], dis1[N + 1];
int fa[N + 1];
int opt[N + 1];
namespace dsu
{
int f[N + 1], sz[N + 1], last[N + 1];
inline void init()
{
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        sz[i] = last[i] = 1;
    }
    return;
}
inline int gfa(int x)
{
    if (f[x] != x)
        f[x] = gfa(f[x]);
    return f[x];
}
inline void merge(int x, int y)
{
    x = gfa(x);
    y = gfa(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x, y);
    sz[x] += sz[y];
    last[x] += last[y];
    f[y] = x;
    return;
}
}
int ans;

inline void addedge(int u, int v, int w)
{
    edge[++tot] = { v, start[u], w };
    start[u] = tot;
    d[u]++;
    edge[++tot] = { u, start[v], w };
    start[v] = tot;
    d[v]++;
    return;
}
inline void dfs(int u)
{
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa[u]) {
            fa[v] = u;
            dfs(v);
        }
    }
    return;
}
inline void dfs1(int u)
{
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa[u]) {
            fa[v] = u;
            dfs1(v);
            if (dis[v] + edge[i].w > dis[u]) {
                dis1[u] = dis[u];
                dis[u] = dis[v] + edge[i].w;
            } else {
                if (dis[v] + edge[i].w > dis1[u])
                    dis1[u] = dis[v] + edge[i].w;
            }
        }
    }
    return;
}
inline void dfs2(int u)
{
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa[u]) {
            if (dis[v] + edge[i].w == dis[u]) {
                if (dis1[u] + edge[i].w > dis[v]) {
                    dis1[v] = dis[v];
                    dis[v] = dis1[u] + edge[i].w;
                } else {
                    if (dis1[u] + edge[i].w > dis1[v])
                        dis1[v] = dis1[u] + edge[i].w;
                }
            } else {
                if (dis[u] + edge[i].w > dis[v]) {
                    dis1[v] = dis[v];
                    dis[v] = dis[u] + edge[i].w;
                } else {
                    if (dis[u] + edge[i].w > dis1[v])
                        dis1[v] = dis[u] + edge[i].w;
                }
            }
            dfs2(v);
        }
    }
    return;
}
inline bool compare(int x, int y)
{
    return dis[x] > dis[y];
}
int main()
{
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        addedge(u, v, w);
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] != 1) {
            dfs1(i);
            dfs2(i);
            break;
        }
    }
    for (int i = 1; i <= n; i++)
        opt[i] = i;
    sort(opt + 1, opt + n + 1, compare);
    fa[opt[n]] = 0;
    dfs(opt[n]);
    q = read();

    while (q--) {
        l = read();
        dsu::init();
        ans = 0;
        int maxx = 1;
        for (int i = 1; i <= n; i++) {
            int u = opt[i];
            for (int j = start[u]; j; j = edge[j].next) {
                int v = edge[j].to;
                if (v != fa[u])
                    dsu::merge(u, v);
            }
            while (dis[opt[maxx]] > dis[u] + l)
                dsu::last[dsu::gfa(opt[maxx++])]--;
            ans = max(ans, dsu::last[dsu::gfa(u)]);
        }
        printf("%d\n", ans);
    }

    return 0;
}