poj1741(点分模板)

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int last[maxn],pre[maxn*],other[maxn*],w[maxn*],t,vis[maxn];

void add(int x,int y,int z){++t;pre[t]=last[x];last[x]=t;other[t]=y;w[t]=z;}

int cnt,root,d[maxn],siz[maxn],f[maxn],sizz,q[maxn];

int x,y,z,n,m,k,ans;

void getroot(int x,int fa){

    siz[x]=;f[x]=;

    for(int i=last[x];i;i=pre[i]){

        int v=other[i];

        if(v==fa||vis[v])continue;

        getroot(v,x);

        siz[x]+=siz[v];

        f[x]=max(f[x],siz[v]);

    }

    f[x]=max(f[x],sizz-siz[x]);

    if(f[x]<f[root])root=x;

}

void getdis(int x,int fa){

    q[++cnt]=d[x];

    for(int i=last[x];i;i=pre[i]){

        int v=other[i];

        if(v==fa||vis[v])continue;

        d[v]=d[x]+w[i];

        getdis(v,x);

    }

}

int calc(int x,int init){

    cnt=;d[x]=init;

    getdis(x,);

    sort(q+,q+cnt+);

    int res=;

    for(int l=,r=cnt;l<r;){

        if(q[l]+q[r]<=k){res+=r-l;l++;}

        else r--;

    }

    return res;

}

void solve(int x){

    ans+=calc(x,);

    vis[x]=;

    for(int i=last[x];i;i=pre[i]){

        int v=other[i];

        if(vis[v])continue;

        ans-=calc(v,w[i]);

        f[]=sizz=siz[v];

        root=;

        getroot(v,);

        solve(root);

    }

}

int main(){

    while(scanf("%d%d",&n,&k)!=EOF){

        if(n==&&k==)break;

        memset(last,,sizeof(last));

        memset(vis,,sizeof(vis));

        t=;

        for(int i=;i<n;++i){

            scanf("%d%d%d",&x,&y,&z);

            add(x,y,z);add(y,x,z);

        }

        f[]=sizz=n;ans=root=;

        getroot(,);

        solve(root);

        printf("%d\n",ans);

    }

    return ;

}