传送门
题意
一棵n点的树，每一个点都从当前位置走到距离最远的位置的距离dis[i]，1~n的连续区间中最大并且走的最远距离差值不超过Q的区间右多大。
分析
感觉有点不好下手
最后的询问是区间最大值减最小值，可以用RMQ实现。
那么就需要处理出每个点从当前位置走到距离最远的位置的距离dis数组了。
直觉上能dfs预处理出来，类似求树的直径，要注意的点是如何处理从父亲结点下来的长度。
这里还是有很多细节的，
需要想清楚，先dfs1出儿子结点（只向下）最远的距离，在dfs2和从父亲结点来的比较。但是如果父亲结点就是从自己更新过去的，自己再由父亲结点更新，就会出错。
故需要维护最大和次大距离。
（看了别人的博客发现这里有个小结论：每个点从当前位置走到距离最远的位置必然是树直径上某一点，所以先找到树的直径两点，再去更新整棵树。也是可以的）
处理出了dis数组，剩下的套一个RMQ就行了。
代码
#include <bits/stdc++.h>using namespace std;
//-----pre_def----
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)//---------------
const int N = 50000 + 10;
int n, m, q;
int h[N], e[N << 1], w[N << 1], ne[N << 1], idx;
int dis[N][2], id[N][2];
int dmax[N][20], dmin[N][20]; //rmq
void init()
{
init_h;memset(dis, 0, sizeof dis);memset(id, 0, sizeof id);
}void add(int a, int b, int c)
{
e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}void cmp(int u, int w, int v) //更新first&&second
{
if (w > dis[u][1]){
dis[u][1] = w;id[u][1] = v;}if (dis[u][0] < dis[u][1]){
swap(dis[u][0], dis[u][1]);swap(id[u][1], id[u][0]);}
}void dfs1(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i]){
int t = e[i];int &len = w[i];if (t == fa)continue;dfs1(t, u);cmp(u, dis[t][0] + len, t); //update}
}void dfs2(int u, int fa, int pre)
{
cmp(u, pre, fa);for (int i = h[u]; ~i; i = ne[i]){
int t = e[i];if (t == fa)continue;dfs2(t, u, (t == id[u][0] ? dis[u][1] : dis[u][0]) + w[i]);}
}void rmq_init()
{
fir(i, 1, n)dmax[i][0] = dmin[i][0] = dis[i][0];for (int k = 1; (1 << k) <= n; k++){
for (int i = 1; i + (1 << k) - 1 <= n; i++){
dmax[i][k] = max(dmax[i][k - 1], dmax[i + (1 << (k - 1))][k - 1]);dmin[i][k] = min(dmin[i][k - 1], dmin[i + (1 << (k - 1))][k - 1]);}}
}int rmq_query(int l, int r)
{
int k = 0;while ((1 << (k + 1)) <= r - l + 1)k++;return max(dmax[l][k], dmax[r - (1 << k) + 1][k]) - min(dmin[l][k], dmin[r - (1 << k) + 1][k]);
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);int StartTime = clock();
#endifwhile (scanf("%d%d", &n, &m), n + m){
init();fir(i, 1, n - 1){
int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);add(b, a, c);}dfs1(1, 0);dfs2(1, 0, 0);rmq_init();fir(i, 1, m){
int ans = 0, mv = 1;scanf("%d", &q);for (int i = 1; i <= n; i++){
while (mv <= i && rmq_query(mv, i) > q)mv++;//cout << i << " " << mv << endl;ans = max(ans, i - mv + 1);}printf("%d\n", ans);}}
#ifndef ONLINE_JUDGEprintf("Run_Time = %d ms\n", clock() - StartTime);
#endifreturn 0;
}