点分治2

题目描述

给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。

输入

第一行输入一个整数 n，表示节点个数。

第二行到第 n 行每行输入三个整数 u,v,w ，表示 u 与 v 有一条边，边权是 w。

第 n+1 行一个整数 k 。

输出

一行一个整数，表示答案。

样例

提示

对于全部的测试点，保证：

• 1\leq n\leq 4\times 10^4。
• 1\leq u,v\leq n。
• 0\leq w\leq 10^3。
• 0\leq k\leq 2\times 10^4。