#include<bits/stdc++.h>
using namespace std;using ll=long long;

/*
题意：每次给定 q，统计树上有多少点对路径最大边权不超过 q。
思路：离线排序询问和边，按边权从小到大加边，并查集维护连通块大小。
每合并大小为 a,b 的两个连通块，新增满足条件点对数为 a*b。
*/

struct E{
    int u,v,w;
};

struct Q{
    int q,id;
};

int n,m;
vector<int> fa,sz;
vector<E> e;
vector<Q> qu;
vector<ll> as;
ll nw;

int fd(int x){
    return fa[x]==x?x:fa[x]=fd(fa[x]);
}

void mg(int x,int y){
    x=fd(x);
    y=fd(y);

    if(x==y)return;

    if(sz[x]<sz[y])swap(x,y);

    nw+=1ll*sz[x]*sz[y];
    fa[y]=x;
    sz[x]+=sz[y];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    e.resize(max(0,n-1));
    qu.resize(m);
    as.resize(m);
    fa.resize(n+1);
    sz.resize(n+1,1);

    for(int i=1;i<=n;i++)fa[i]=i;

    for(int i=0;i<n-1;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }

    for(int i=0;i<m;i++){
        cin>>qu[i].q;
        qu[i].id=i;
    }

    sort(e.begin(),e.end(),[](E a,E b){
        return a.w<b.w;
    });

    sort(qu.begin(),qu.end(),[](Q a,Q b){
        return a.q<b.q;
    });

    int j=0;

    for(auto x:qu){
        while(j<n-1&&e[j].w<=x.q){
            mg(e[j].u,e[j].v);
            j++;
        }
        as[x.id]=nw;
    }

    for(int i=0;i<m;i++){
        if(i)cout<<" ";
        cout<<as[i];
    }

    return 0;
}

这题可以把一个询问 q 理解成：只保留边权 <= q 的边。

因为原图是一棵树，任意两个点之间只有一条简单路径。
如果两个点在保留下来的图中连通，说明它们路径上的所有边都被保留下来了，也就是路径最大边权不超过 q。

所以问题变成：

对于每个 q，统计只加入边权 <= q 的边后，每个连通块内部有多少点对。

如果每次询问都重新建图，复杂度会很高。
注意到询问值越大，能加入的边只会变多，不会减少，所以可以离线处理。

做法是：

1. 把所有边按边权从小到大排序。
2. 把所有询问按 q 从小到大排序，同时记录原编号。
3. 用并查集维护当前已经加入的边形成的连通块。
4. 对每个询问，把所有边权 <= q 的边加入。
5. 当前满足条件的点对数就是答案。

关键是合并两个连通块时答案怎么变化。

假设两个连通块大小分别为 a 和 b。
合并前，这两个连通块之间的点对不连通，不满足条件。
合并后，从第一个连通块选一个点，从第二个连通块选一个点，都变成满足条件的点对。

所以新增点对数量为：

a * b

用变量 nw 维护当前答案。
每合并两个不同连通块，就让：

nw += a * b

最后把每个询问的答案存回原编号，按输入顺序输出。

时间复杂度：

O((n + m) log(n + m))

主要来自边排序和询问排序。

空间复杂度：

O(n + m)