EEE

题目中问到关于所有路径的问题，这样我们很自然就能想到需要通过点分治来解决此类问题（我跟你讲淀粉质可好吃了），然后我们需要进一步解决的就是如何快速统计之后的答案，题目中出题人很良心的告诉了∑z的数据范围1≤∑z≤2×10^5所以我可以统计一个前缀和然后二分查找答案（zz的storm竟然写了一个treap，然后T了），这个二分可以通过STL的lower_bound实现，然后我们这样写就过了。所以这道题实质上是一道非常好的点分治的模板题。
经过出题人的提醒，我才意识到这个做法是错误的。对于一个菊花图来说，如果用一个桶来更新的话，我们的更新复杂度可能会被卡到S^2（S=路径的个数），这样对于这个题来说是不可以通过的，那么我们就需要来优化复杂度，通过观察我们统计答案的步骤我们可以，得到一个a[]数组，角标i就是表示路径长度为i的个数，这样我们就可以用每次getdis()更新的路径与他卷积之后就可以更新答案，最后统计答案的做法不变。经过我的不懈努力终于写了出来，提交之后会发现T掉了最后10%的数据，在看了题解区dalao的评论之后，我发现这个做法并不会是官方题解给出复杂度严格SlogS如果一直统计较大的路径这种做法也会劣化，我们采取的做法是由路径长度由小到大更新。
最后吐槽一句，这个题不卡N^2暴力不卡裸的点分治，而且正解NTT竟然会比N^2暴力还慢？

#include<cstdio>
#include<set>
#include<iostream>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 1000010
#define maxs 1000010
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const double pie=acos(-1);

namespace IO {
    template <typename T>
    inline void w(T x) { if (x > 9) w(x / 10); putchar(x % 10 + 48); }
    template <typename T>
    inline void write(T x, char c) { if(x < 0) putchar('-'), x = -x; w(x); putchar(c); }
    template <typename T>
    inline void read(T &x) {
        x = 0; T f = 1; char c = getchar();
        for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
        for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
        x *= f;
    }
};

int e[maxn],ne[maxn],h[maxn],cst[maxn],bit,dis[maxn],idx=1,sz[maxn],maxx[maxn],sum,root,ans[maxs],rev[maxs],lena,lenb,a[maxs],b[maxs],tot,maxdep;
bool vis[maxn];

void add(int a,int b,int c){
    e[idx]=b;ne[idx]=h[a];cst[idx]=c;h[a]=idx++;
    e[idx]=a;ne[idx]=h[b];cst[idx]=c;h[b]=idx++;
}

struct cp{
    double real,imaginary;
    cp operator +(cp that){
        return (cp){real+that.real,imaginary+that.imaginary};
    }
    cp operator -(cp that){
        return (cp){real-that.real,imaginary-that.imaginary};
    }
    cp operator *(cp that){
        return (cp){real*that.real-imaginary*that.imaginary,imaginary*that.real+real*that.imaginary};
    }
}f[maxn],g[maxn];

void FFT(cp *F,int len,int flag){
    for(int i=1;i<len;i++){
        rev[i]=(rev[i>>1]>>1|(i&1)<<bit);
        if(i<rev[i])
            swap(F[i],F[rev[i]]);
    }
    for(int i=1;i<len;i<<=1){
        cp x,y,wn={cos(pie/i),flag*sin(pie/i)};
        for(int j=0,add=i<<1;j<len;j+=add){
            cp w=(cp){1,0};
            for(int k=0;k<i;k++,w=w*wn){
                x=F[j+k];y=w*F[i+j+k];
                F[j+k]=x+y;F[i+j+k]=x-y;  
            }
        }
    }
    return;
}

void work(int n,int m){
    int len=1;
    bit=0;
    while(len<=n+m){
        len<<=1;
        bit++;
    }bit--;
    for(int i=0;i<=n;i++)
        f[i].real=(double)a[i];
    for(int i=0;i<=m;i++){
        g[i].real=(double)b[i];
        a[i]+=b[i];
        b[i]=0;
    }
    lena=max(n,m);
    FFT(f,len,1);FFT(g,len,1);
    for(int i=0;i<=len;i++)
        f[i]=f[i]*g[i];
    FFT(f,len,-1);
    for(int i=0;i<=n+m;i++)
        ans[i]+=(int)(f[i].real/len+0.5);
    for(int i=0;i<len;i++)
        f[i].real=f[i].imaginary=g[i].real=g[i].imaginary=0.0;
    return;
}
void getroot(int u,int fa){
    sz[u]=1;
    maxx[u]=0;
    for(int i=h[u];i;i=ne[i]){
        if(e[i]==fa||vis[e[i]])
            continue;
        getroot(e[i],u);
        sz[u]+=sz[e[i]];
        maxx[u]=max(maxx[u],sz[e[i]]);
    }
    maxx[u]=max(maxx[u],sum-maxx[u]);
    if(maxx[root]>maxx[u]){
        root=u;
    }
    return;
}

void getdis(int u,int fa){
    b[dis[u]]++;
    if(lenb<dis[u])
        lenb=dis[u];
    for(int i=h[u];i;i=ne[i]){
        if(e[i]==fa||vis[e[i]])
            continue;
        dis[e[i]]=dis[u]+cst[i];
        getdis(e[i],u);
    }
}

struct Son {
    int v,c,d;
    bool operator<(const Son &b) const {
        return d < b.d;
    }
} sons[maxn];

void getdep(int u,int fa,int dep){
    maxdep=max(maxdep,dep);
    for(int i=h[u];i;i=ne[i]){
        if(vis[u]||e[i]==fa) continue;
        getdep(e[i],u,dep+cst[i]);
    }
}

void clac(int u){
    a[0]=1;lena=1;tot=0;
    for(int i=h[u];i;i=ne[i]){
        if(vis[e[i]]) continue;
        maxdep=0;
        getdep(e[i],u,cst[i]);
        sons[tot++]=(Son){e[i],cst[i],maxdep};
    }
    sort(sons,sons+tot);
    for(int i=0;i<tot;i++){
        int v=sons[i].v,w=sons[i].c;
        lenb=-1;
        dis[v]=w;
        getdis(v,u);
        work(lena,lenb);
    }
    for(int i=0;i<=lena;i++){
        a[i]=0;
    }
    return;
}

void solve(int u){
    vis[u]=true;
    clac(u);
    for(int i=h[u];i;i=ne[i]){
        if(vis[e[i]]) continue;
        sum=sz[e[i]];
        root=0;
        getroot(e[i],0);
        solve(root);
    }
    return;
}

using namespace IO;
int main(){
    srand(time(0));
    int n,m,x,y,z,k;
    IO::read(n);
    read(m);
    for(int i=1;i<n;i++){
        read(x);
        read(y);
        read(z);
        add(x,y,z);
    }
    sum=n;
    root=0;
    maxx[0]=INF;
    getroot(1,0);
    solve(root);
    for(int i=1;i<=200000;i++){
        ans[i]+=ans[i-1];
    }
    while(m--){
        read(k);
        k=lower_bound(ans,ans+200001,k)-ans;
        printf("%d\n",k);
    }
    return 0;
}