C++(clang++11) 解法, 执行用时: 1929ms, 内存消耗: 15196K, 提交时间: 2021-01-20 21:34:16

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
using namespace std;
typedef long long ll;
typedef double db;
const int N=2e5+5;
const db eps=1e-4;
struct EDGE
{
	int y,z;
};
vector<EDGE> b[N];
int dis[N],dfn[N],rcn[N],td,n,q,i,x,y,z,k,pos;
int cnt[N],Ref[N];
void dfs(int x,int y)
{
	for (auto i:b[x])
	if (i.y!=y)
	{
		dis[i.y]=dis[x]+i.z;
		dfs(i.y,x);
	}
}
void solve(int x,int y)
{
	dfn[x]=++td;
	Ref[td]=x;
	for (auto i:b[x]) if (i.y!=y)
		solve(i.y,x);
	rcn[x]=td;
	int c=dis[x],j,k;
	for (auto i:b[x])
	if (i.y!=y) 
	{
		fo(j,dfn[i.y],rcn[i.y])
		{
			cnt[dis[Ref[j]]-c]++;
			fo(k,rcn[i.y]+1,rcn[x])
				cnt[dis[Ref[j]]+dis[Ref[k]]-c*2]++;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	fo(i,1,n-1)
	{
		scanf("%d %d %d",&x,&y,&z);
		b[x].push_back({y,z});
		b[y].push_back({x,z});
	} 
	dfs(1,0);
	solve(1,0);
	int mx=2e5;
	fo(i,1,mx)
		cnt[i]+=cnt[i-1];
	fo(i,1,q)
	{
		scanf("%d",&k);
		pos=lower_bound(cnt+1,cnt+1+mx,k)-cnt;
		printf("%d\n",pos);
	}
}