#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define Max 1000001
#define MAXN 1000005
#define MOD 1000000007
#define rin freopen("in.txt","r",stdin)
#define rout freopen("1.out","w",stdout)
#define Del(a,b) memset(a,b,sizeof(a))
typedef long long LL;
using namespace std;
const int N = 50100;
int T;
struct Node {
int to;
int cap;
};
vector<Node> v[N];
int dp[N][4];
int maxsum[N][25];
int minsum[N][25];
int logg[N];
void Init() {
logg[0] = -1;
for (int i = 1; i <= N; i++)
logg[i] = logg[i >> 1] + 1; //logg[i]表示int logg2(i)
}
void dfs1(int father) {
int mast = 0;
int maer = 0;
for (int i = 0; i < v[father].size(); i++) {
Node child = v[father][i];
dfs1(child.to);
int cost = dp[child.to][0] + child.cap;
if (cost >= mast) {
maer = mast;
mast = cost;
} else if (cost > maer) {
maer = cost;
}
}
dp[father][0] = mast;
dp[father][1] = maer;
}
void dfs2(int root) {
for (int i = 0; i < v[root].size(); i++) {
Node child = v[root][i];
dp[child.to][2] = max(dp[root][2],
dp[child.to][0] + child.cap == dp[root][0] ?
dp[root][1] : dp[root][0]) + child.cap;
dfs2(child.to);
}
}
void RMQ(int n)
{
for (int j = 1; j < 20; ++j)
for (int i = 1; i <= n; ++i)
if (i + (1 << j) - 1 <= n) {
maxsum[i][j] = max(maxsum[i][j - 1],
maxsum[i + (1 << (j - 1))][j - 1]);
minsum[i][j] = min(minsum[i][j - 1],
minsum[i + (1 << (j - 1))][j - 1]);
}
}
int rmq_min(int l, int r) {
int tmp = logg[r - l + 1];
int a = max(maxsum[l][tmp], maxsum[r - (1 << tmp) + 1][tmp]);
int b = min(minsum[l][tmp], minsum[r - (1 << tmp) + 1][tmp]);
return a - b;
}
int main() {
rin;
int n, m;
Init();
while (scanf("%d%d", &n, &m) && n + m) {
for (int i = 1; i <= n - 1; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
int maxnode = max(x, y);
int minnode = min(x, y);
Node tmp;
tmp.cap = z;
tmp.to = maxnode;
v[minnode].push_back(tmp);
}
Del(dp, 0);
dfs1(1);
dp[1][2] = 0;
dfs2(1);
for (int i = 1; i <= n; i++) {
maxsum[i][0] = max(dp[i][0], dp[i][2]);
minsum[i][0] = max(dp[i][0], dp[i][2]);
}
RMQ(n);
for (int i = 0; i < m; i++) {
int Q;
scanf("%d", &Q);
int l = 1, r = 1, ans = 0;
while (l <= n && r <= n) {
if (rmq_min(l, r) <= Q) {
ans = max(ans, r - l + 1);
r++;
} else
l++;
}
printf("%d\n", ans);
}
for (int i = 1; i <= n; i++) {
v[i].clear();
}
}
return 0;
}
来源: http://www.bubuko.com/infodetail-2266081.html