题目分析

Bob想要举办一场比赛，比赛规则如下：

1. 村庄结构：村庄有N栋房子和N-1条路，形成一个树形结构（所有房子互相连通且无环）。
2. 比赛规则：
   • 每个参赛者从不同的房子出发。
   • 参赛者需要尽可能跑得远，且不能重复经过同一条路。
   • 跑得最远的人和跑得最短的人之间的距离差称为“种族差”。
   • Bob希望“种族差”不超过给定的Q。
   • 起始房子必须是连续的编号。
3. 问题目标：对于每个查询Q，求出在“种族差”不超过Q的情况下，最多可以有多少人参加比赛（即最大的连续起始房子数量）。

解题思路

1. 树的最长路径（直径）：

   • 对于树中的每个节点，我们需要计算从该节点出发能够跑的最远距离。这可以通过两次DFS或BFS来计算树的直径及其端点。
   • 具体来说：
     • 第一次DFS从任意节点出发，找到距离最远的节点u。
     • 第二次DFS从u出发，找到距离最远的节点v。
     • 对于每个节点，其最长跑动距离是到u或v的距离中的较大值。

2. 预处理每个节点的最远距离：

   • 使用DFS或BFS计算每个节点的最远跑动距离，存储在数组s中。

3. 滑动窗口与RMQ：

   • 我们需要找到最长的连续子数组，使得子数组中的最大值与最小值之差不超过Q。
   • 使用滑动窗口（双指针）技术：
     • 维护一个窗口[head, tail]，初始时head = tail = 1。
     • 如果当前窗口的“种族差”（最大值-最小值）≤ Q，则尝试扩展窗口（tail++）。
     • 否则，收缩窗口（head++）。
   • 为了高效查询窗口内的最大值和最小值，使用RMQ（Range Minimum/Maximum Query）数据结构：
     • 使用稀疏表（Sparse Table）预处理s数组，支持O(1)时间的区间最值查询。

代码实现步骤

1. 输入处理：

   • 读取N和M，直到N和M都为0时结束。
   • 对于每个测试用例，读取N-1条边的信息，构建树的邻接表。

2. 计算每个节点的最远距离：

   • 第一次DFS从根节点（如节点1）出发，计算每个节点到其子树的最远距离和次远距离，并记录最远距离的子节点。
   • 第二次DFS从根节点出发，计算每个节点通过父节点能够到达的最远距离。

3. 构建RMQ稀疏表：

   • 预处理s数组，构建MIN和MAX稀疏表，用于快速查询区间最小值和最大值。

4. 处理查询：

   • 对于每个查询Q，使用滑动窗口和RMQ找到最长的连续子数组，使得最大值与最小值之差≤ Q。

复杂度分析

1. DFS计算最远距离：O(N)，每个节点被访问两次。
2. 构建RMQ稀疏表：O(N log N)，预处理时间。
3. 处理查询：
   • 每个查询使用滑动窗口和RMQ，复杂度为O(N)（每个元素最多被访问两次）。
   • 总查询复杂度为O(M N)。

对于N≤50000和M≤500，总复杂度为O(N log N + M N)，在时间限制内是可接受的。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

struct gtype {
    int y, d, next;
} g[100010];
int first[50010], tot, x, y, d, s[50010], a[50010][4], n, m, q;
int MIN[50001][20], MAX[50001][20];

void add(int x, int y, int d) {
    tot++;
    g[tot].y = y;
    g[tot].d = d;
    g[tot].next = first[x];
    first[x] = tot;
}

int dfs(int x, int fa) {
    int tmp1 = 0, tmp2 = 0, vx = 0;
    for (int t = first[x]; t != -1; t = g[t].next) {
        int y = g[t].y;
        if (y == fa) continue;
        int tmp = g[t].d + dfs(y, x);
        if (tmp > tmp1) {
            tmp2 = tmp1;
            tmp1 = tmp;
            vx = y;
        } else if (tmp > tmp2) {
            tmp2 = tmp;
        }
    }
    a[x][0] = vx;
    a[x][1] = tmp1;
    a[x][2] = tmp2;
    return tmp1;
}

void find(int x, int fa, int ans) {
    int vx = a[x][0];
    int tmp1 = a[x][1];
    int tmp2 = a[x][2];
    if (ans > tmp1) {
        tmp2 = tmp1;
        tmp1 = ans;
        vx = 0;
    } else if (ans > tmp2) {
        tmp2 = ans;
    }
    s[x - 1] = tmp1;
    for (int t = first[x]; t != -1; t = g[t].next) {
        int y = g[t].y;
        if (y == fa) continue;
        if (y == vx) {
            find(y, x, tmp2 + g[t].d);
        } else {
            find(y, x, tmp1 + g[t].d);
        }
    }
}

int max(int x, int y) {
    return s[x] > s[y] ? x : y;
}

int min(int x, int y) {
    return s[x] > s[y] ? y : x;
}

void ST() {
    int i, j;
    for (i = 0; i <= n; i++) {
        MIN[i][0] = MAX[i][0] = i;
    }
    for (j = 1; (1 << j) <= n; j++) {
        for (i = 0; i + (1 << j) - 1 < n; i++) {
            MIN[i][j] = min(MIN[i][j - 1], MIN[i + (1 << (j - 1))][j - 1]);
            MAX[i][j] = max(MAX[i][j - 1], MAX[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int RMQ(int i, int j, int x) {
    if (i > j) {
        i ^= j; j ^= i; i ^= j;
    }
    int k = 0;
    while (i + (1 << k) < j - (1 << k) + 1) k++;
    if (x == 1) {
        return max(MAX[i][k], MAX[j - (1 << k) + 1][k]);
    }
    return min(MIN[i][k], MIN[j - (1 << k) + 1][k]);
}

int maxi(int a, int b) {
    return a > b ? a : b;
}

int main() {
    while (scanf("%d%d", &n, &m)) {
        if (n == 0 && m == 0) break;
        tot = 0;
        memset(g, 0, sizeof(g));
        memset(first, -1, sizeof(first));
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &x, &y, &d);
            add(x, y, d);
            add(y, x, d);
        }
        dfs(1, 0);
        find(1, 0, 0);
        ST();
        for (int i = 1; i <= m; i++) {
            scanf("%d", &q);
            int head = 1, tail = 1, ans = 0;
            while (tail <= n) {
                int tmp1 = s[RMQ(head - 1, tail - 1, 0)];
                int tmp2 = s[RMQ(head - 1, tail - 1, 1)];
                if (tmp2 - tmp1 <= q) {
                    tail++;
                    ans = maxi(ans, tail - head);
                } else {
                    head++;
                    tail++;
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}