poj1741 Tree

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
const int N=1e5+5;
const int inf=0x3f3f3f3f;
using namespace std;
int n,k,cnt,head[N],son[N],f[N],sum,ans,root,d[N],deep[N];
bool vis[N];
struct node
{
    int next,to,w;
}e[2*N];
inline void add(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].to=u;e[cnt].w=w;e[cnt].next=head[v];head[v]=cnt;
}
inline void getroot(int x,int fa)
{
    son[x]=1;f[x]=0;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa||vis[e[i].to]) continue;
        getroot(e[i].to,x);
        son[x]+=son[e[i].to];
        f[x]=max(f[x],son[e[i].to]);
    }
    f[x]=max(f[x],sum-son[x]);
    if(f[x]<f[root]) root=x;
}
inline void getdeep(int x,int fa)
{
    deep[++deep[0]]=d[x];
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa||vis[e[i].to]) continue;
        d[e[i].to]=d[x]+e[i].w;
        getdeep(e[i].to,x);
    }
}
inline int cal(int x,int p)
{
    d[x]=p;deep[0]=0;
    getdeep(x,0);
    sort(deep+1,deep+deep[0]+1);
    int t=0,l,r;
    for(l=1,r=deep[0];l<r;)
    {
        if(deep[l]+deep[r]<=k) {t+=r-l;l++;}
        else r--;
    } 
    return t;
}
inline void work(int x)
{
    ans+=cal(x,0);
    vis[x]=true;
    for(int i=head[x];i;i=e[i].next)
    {
        if(vis[e[i].to]) continue;
        ans-=cal(e[i].to,e[i].w);
        sum=son[e[i].to];
        root=0;
        getroot(e[i].to,0);
        work(root);
    }
}
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("a.out","w",stdout);
    while(scanf("%d%d",&n,&k)==2 && n!=0)
    {
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis)); 
        int u,v,w; cnt=0;
        for(int i=1;i<n;i++)
        {
               scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);        
        }
        sum=n; f[0]=inf;
        getroot(1,0); 
        ans=0; 
        work(root);
           printf("%d\n",ans);
    }
}