/*思路：最容易想到的算法是：从每个点出发遍历整棵树，统计数对个数。由于时间复杂度O(N^2)，明显是无法满足要求的。对于一棵有根树， 树中满足要求的一个数对所对应的一条路径，必然是以下两种情况之一：1、经过根节点2、不经过根节点，也就是说在根节点的一棵子树中对于情况2，可以递归求解，下面主要来考虑情况1。设点i的深度为Depth[i]，父亲为Parent[i]。若i为根，则Belong[i]=-1，若Parent[i]为根，则Belong[i]=i，否则Belong[i]=Belong[Parent[i]]。这三个量都可以通过一次BFS求得。我们的目标是要统计：有多少对(i,j)满足i<j，Depth[i]+Depth[j]<=K且Belong[i]<>Belong[j]如果这样考虑问题会变得比较麻烦，我们可以考虑换一种角度：设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数设Y为满足i<j，Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数那么我们要统计的量便等于X-Y求X、Y的过程均可以转化为以下问题：已知A[1],A[2],...A[m]，求满足i<j且A[i]+A[j]<=K的数对(i,j)的个数对于这个问题，我们先将A从小到大排序。设B[i]表示满足A[i]+A[p]<=K的最大的p(若不存在则为0)。我们的任务便转化为求出A所对应的B数组。那么，若B[i]>i，那么i对答案的贡献为B[i]-i。显然，随着i的增大，B[i]的值是不会增大的。利用这个性质，我们可以在线性的时间内求出B数组，从而得到答案。综上，设递归最大层数为L，因为每一层的时间复杂度均为“瓶颈”——排序的时间复杂度O(NlogN)，所以总的时间复杂度为O(L*NlogN)然而，如果遇到极端情况——这棵树是一根链，那么随意分割势必会导致层数达到O(N)级别，对于N=10000的数据是无法承受的。因此，我们在每一棵子树中选择“最优”的点分割。所谓“最优”，是指删除这个点后最大的子树尽量小。这个点可以通过树形DP在O(N)时间内求出，不会增加时间复杂度。这样一来，即使是遇到一根链的情况时，L的值也仅仅是O(logN)的。因此，改进后算法时间复杂度为O(Nlog^2N)，可以AC。/*

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define inf 0x3f3f3f3f#define maxn 40010using namespace std;struct node{    int to,w,next;}e[maxn<<1];int head[maxn],vis[maxn],son[maxn],deep[maxn],f[maxn],d[maxn];int n,cnt,root,sum,K,ans,num,x,y,z,L;inline int read(){    int x=0,f=1;char c=getchar();    while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}inline void add(int u,int v,int dis){    e[++num].to=v;e[num].next=head[u];    e[num].w=dis;head[u]=num;}inline void init(){    cnt=ans=root=sum=0;    memset(head,0,sizeof(head));    memset(vis,0,sizeof(vis));    memset(deep,0,sizeof(deep));    for(int i=1;i<n;i++)    {        x=read();y=read();z=read();        add(x,y,z);add(y,x,z);    }}void get_root(int now,int fa){    son[now]=1;f[now]=-1;    for(int i=head[now];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]||v==fa) continue;        get_root(v,now);        son[now]+=son[v];f[now]=max(f[now],son[v]);    }    f[now]=max(f[now],sum-son[now]);    if(f[now]<f[root]) root=now;}void get_deep(int now,int fa){    deep[++L]=d[now];    for(int i=head[now];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]||v==fa) continue;        d[v]=d[now]+e[i].w;        get_deep(v,now);    }}int cal(int now,int dis){    d[now]=dis;L=0;get_deep(now,-1);    sort(deep+1,deep+L+1);    int t=0;    for(int l=1,r=L;l<r;)    {        if (deep[l]+deep[r]<=K) t+=r-l,l++;        else r--;            }    return t;}void work(int u){    ans+=cal(u,0);vis[u]=1;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]) continue;        ans-=cal(v,e[i].w);sum=son[v];        root=0;get_root(v,0);work(root);    }}int main() {    freopen("data.txt","r",stdin);    freopen("bzoj1468.txt","w",stdout);    n=read();    init();K=read();    sum=n;f[0]=inf;    get_root(1,-1);    work(root);    printf("%d\n",ans);    return 0;}

#include<cstdio>#include<algorithm>#define N 40005using namespace std;struct arr{int s,go,next;}a[N*2];int end[N],son[N],f[N],d[N],data[N];int cnt,L,All,ans,i,x,y,z,n,root,K;bool Can[N];void add(int u,int v,int s){  a[++cnt].go=v;a[cnt].next=end[u];a[cnt].s=s;end[u]=cnt;}void Get_root(int k,int fa){  son[k]=1;f[k]=0;  for (int i=end[k];i;i=a[i].next)  {    int go=a[i].go;    if (go==fa||Can[go]) continue;    Get_root(go,k);son[k]+=son[go];    if (son[go]>f[k]) f[k]=son[go];  }  if (All-son[k]>f[k]) f[k]=All-son[k];  if (f[k]<f[root]) root=k;}void Get_array(int k,int fa){  data[++L]=d[k];  for (int i=end[k];i;i=a[i].next)  {    int go=a[i].go;    if (go!=fa&&!Can[go])       d[go]=d[k]+a[i].s,Get_array(go,k);  }}int calc(int k,int now){  d[k]=now;L=0;Get_array(k,-1);  int A=0,l,r;  sort(data+1,data+L+1);  for (l=1,r=L;l<r;)    if (data[r]+data[l]<=K) A+=(r-l),l++;else r--;  return A;}void work(int k){  ans+=calc(k,0);Can[k]=1;  for (int i=end[k];i;i=a[i].next)  {    int go=a[i].go;    if (Can[go]) continue;    ans-=calc(go,a[i].s);f[root=0]=n+1;    All=son[go];Get_root(go,-1);    work(root);  }}int main(){    freopen("data.txt","r",stdin);    freopen("1468.txt","w",stdout);  scanf("%d",&n);  for (i=1;i<n;i++)    scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);  scanf("%d",&K);All=n;  f[root=0]=n+1;Get_root(1,-1);  work(root);  printf("%d",ans);  return 0;}

#include <bits/stdc++.h>using namespace std;#define PaiChuCuoWuCaiBREAK trueint main(){    while(PaiChuCuoWuCaiBREAK)    {        system("data.exe");        system("1468.exe");        system("bzoj1468.exe");        if(system("fc 1468.txt bzoj1468.txt")) {cout<<"lrhdsb";break;}    }    return 0;}

#include <bits/stdc++.h>using namespace std;#define maxn 10004#define justval 68451#define justval_ 15641684int l[maxn],r[maxn],n,lo,ro;int main(){    freopen("data.txt","w",stdout);    n=rand()%maxn+1;printf("%d\n",n);    for(int i=1;i<n;i++) l[i]=i+1;    lo=n-1,r[++ro]=1;    for(int just=1;just<n;just++)    {        int pos=rand()%lo+1;        int pos_=rand()%ro+1;        r[++ro]=l[pos];        printf("%d %d %d\n",l[pos],r[pos_],rand()%justval);        for(int i=pos;i<lo;i++) l[i]=l[i+1];lo--;    }    printf("%d\n",rand()%justval_);    return 0;}