给你一棵树，边有边权，定义 \(f_x=\max_{i=1}^n\operatorname{dist}(x,i)\)。\(q\) 次询问，每次给出一个数 \(l\) 求最大的连通块 \(s\) 满足 \(\max_{x\in s}f_x-\min_{x\in s}f_x\le l\)。\(n\le 10^5,q\le 50\)。
首先假设这棵树的直径的两个端点为 \(u,v\)，不难发现 \(f_x=\max(\operatorname{dist}(u,x)\operatorname{v,x})\)。这个用证明直径的方法可以证明。
然后我们需要发现一个性质，那就是将点按照 \(f\) 从大到小排序，那么儿子一定排在父亲的前面。
然后就好办了，我们考虑将点按 \(f\) 从大到小排序，然后我们考虑在上面 two points，一边用并查集维护两个指针所在区间的联通性，插入一个点直接将其儿子合并，删除节点是发现只会删除叶子节点，不会改变连通性，只要把该连通块 size 减掉即可。
cpp
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x * 10) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
#define lowbit(x) (x & -x)
namespace dfcmd {
const int maxn = 100005;
typedef long long LL;
int n, q;
struct Edge {
int to, nxt;
LL dist;
} e[maxn << 1];
int first[maxn];
inline void add_edge(int from, int to, LL dist) {
static int cnt = 0;
e[++cnt].nxt = first[from];
first[from] = cnt;
e[cnt].to = to;
e[cnt].dist = dist;
e[++cnt].nxt = first[to];
first[to] = cnt;
e[cnt].to = from;
e[cnt].dist = dist;
}
LL v[maxn];
int vis[maxn];
inline int bfs(int from) {
memset(vis, 0, sizeof(vis));
queue<pair<int, LL>> q;
q.emplace(from, 0);
int ans = 0;
LL dd = 0;
while (!q.empty()) {
int now = q.front().first;
LL d = q.front().second;
q.pop();
vis[now] = 1;
if (d > dd) {
dd = d;
ans = now;
}
v[now] = max(v[now], d);
for (int i = first[now]; i; i = e[i].nxt) {
int to = e[i].to;
if (!vis[to]) {
q.emplace(to, d + e[i].dist);
}
}
}
return ans;
}
inline void getrt() {
bfs(bfs(bfs(1)));
}
int rt;
LL l;
int no[maxn];
inline bool cmp(int x, int y) {
return v[x] < v[y];
}
namespace DFCDM {
int fa[maxn];
int siz[maxn];
int Fa[maxn];
inline int getfa(int x) {
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
inline void dfs(int now) {
for (int i = first[now]; i; i = e[i].nxt) {
int to = e[i].to;
if (to != Fa[now]) {
Fa[to] = now;
dfs(to);
}
}
}
inline int solve() {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
siz[i] = 1;
}
int ans = 0;
for (int rr = n, ll = n; rr; --rr) {
while (ll - 1 && v[no[rr]] - v[no[ll - 1]] <= l) {
ll--;
for (int i = first[no[ll]]; i; i = e[i].nxt) {
int to = e[i].to;
if (to != Fa[no[ll]]) {
int fax = getfa(no[ll]);
int fay = getfa(to);
fa[fay] = fax;
siz[fax] += siz[fay];
}
}
ans = max(ans, siz[getfa(no[ll])]);
}
siz[getfa(no[rr])]--;
}
return ans;
}
}
int Main() {
read(n);
for (int i = 1; i < n; ++i) {
int u, v;
LL d;
read(u), read(v), read(d);
add_edge(u, v, d);
}
getrt();
for (int i = 1; i <= n; ++i) {
no[i] = i;
}
sort(no + 1, no + n + 1, cmp);
DFCDM::dfs(no[1]);
read(q);
while (q--) {
read(l);
writeln(DFCDM::solve());
}
return 0;
}
}
int main() {
return dfcmd::Main();
}