60分WA了四个

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int MAXN = 1e6 + 17;
const int INF = 1e9 + 17;

struct node
{
	int v,next,w;
}e[MAXN];

int size[MAXN],maxx[MAXN],head[MAXN],sum,rt,cnt,tot;
ll d[MAXN],dd[MAXN],k,ans;
bool vis[MAXN];

void add(int u,int v,int w)
{
	e[++tot].next = head[u];
	e[tot].v = v;
	e[tot].w = w;
	head[u] = tot;
}

void getG(int u,int fa)
{
	size[u] = 1;
	maxx[u] = 0;
	for(int i = head[u];i;i = e[i].next)
	{
		int v = e[i].v;
		if(v == fa || vis[v])continue;
		getG(v,u);
		maxx[u] = max(maxx[u],size[v]);
		size[u] += size[v];
	}
	maxx[u] = max(maxx[u],sum - maxx[u]);
	if(maxx[u] < maxx[rt])rt = u;
}

void getdis(int u,int fa)
{
	int now = cnt;
	for(int i = head[u];i;i = e[i].next)
	{
		int v = e[i].v;
		int w = e[i].w;
		if(v == fa || vis[v])continue;
		d[++cnt] = d[now] + w;
		getdis(v,u);
	}
}

void charge(int l,int r)
{
	int i = 1;
	int j = l;
	int L = 0;
	while(i < l && j <= r)
	{
		if(d[i] < d[j])dd[++L] = d[i++];
		else dd[++L] = d[j++];
	}
	if(i < l)
		for(int p = i;p < l;p += 1)
			d[L + p - i + 1] = d[p];
	if(j <= r)
		for(int p = j;p <= r;p += 1)
			d[L + p - j + 1] = d[p];	
	for(int p = 1;p <= L;p += 1)
		d[p] = dd[p];
}

void dfs(int u,int fa)
{
	cnt = 1;
	d[1] = 0;
	vis[u] = 1;
	int l,r;
	for(int i = head[u];i;i = e[i].next)
	{
		int v = e[i].v;
		int w = e[i].w;
		if(v == fa || vis[v])continue;
		l = cnt + 1;
		d[++cnt] = w;
		getdis(v,u);
		r = cnt;
		sort(d + l,d + r + 1);
		for(int x = 1,y = cnt;y >= l && x < l;x += 1)
		{
			while(d[x] + d[y] > k && y >= l)y--;
			if(y < l)break;
			if(d[x] + d[y] <= k)ans += y - l + 1;
		}
		/*for(int x = 1;x <= cnt;x += 1)
			cout << d[x] << ' ';
		cout << endl;*/
		charge(l,r);
	}
	for(int i = head[u];i;i = e[i].next)
	{
		int v = e[i].v;
		if(v == fa || vis[v])continue;
		sum = size[v];
		rt = 0;
		maxx[0] = INF;
		getG(v,u);
		getG(rt,-1);
		dfs(rt,u);
	}
}

int main()
{
	int n;
	cin >> n;
	for(int i = 1,u,v,w;i < n;i += 1)
	{
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
	}
	cin >> k;
	sum = n;
	rt = 0;
	maxx[0] = INF;
	getG(1,-1);
	getG(rt,-1);
	dfs(rt,-1);
	cout << ans << endl;
	return 0;
}