#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAX_N 11000

struct tnode { int t, w, n; };

tnode e[MAX_N * 2];
int fi[MAX_N], d[MAX_N], size[MAX_N];
int f[MAX_N];
bool used[MAX_N];
int tot, rs, root, sx;
int n, m, es;

void inserte(int x, int y, int z)
{
     e[++es].t = y, e[es].w = z, e[es].n = fi[x], fi[x] = es;
}

void init(void)
{
     memset (fi, -1, sizeof (fi));
     memset (used, false, sizeof (used));
     es = -1;
     for (int i = 1, x, y, z; i < n; i++)
     {
         scanf ("%d%d%d", &x, &y, &z);
         inserte (x, y, z);
         inserte (y, x, z);
     }
}

void get_root(int x, int p)
{
     int big = -1;
     size[x] = 1;
     for (int i = fi[x], t; i != -1; i = e[i].n)
     {
         t = e[i].t;
         if (used[t] || t == p) continue;
         get_root (t, x);
         size[x] += size[t];
         if (size[t] > big) big = size[t];
     }
     if (sx - size[x] > big) big = sx - size[x];
     if (big < rs) rs = big, root = x;
}

void get_dis(int x, int dis, int p)
{
     d[++tot] = dis;
     for (int i = fi[x], t; i != -1; i = e[i].n)
     {
         t = e[i].t;
         if (used[t] || t == p) continue;
         get_dis (t, dis + e[i].w, x);
     }
}

int count(int x, int y)
{
    int s = 0;
    tot = 0, get_dis (x, y, -1);
    sort (d + 1, d + tot + 1);
    for (int i = 1, j = tot; i <= j; i++)
    {
        while (d[i] + d[j] > m && i <= j) j--;
        if (i < j) s += j - i;
    }
    return s;
}

int find_root(int x)
{
    rs = sx = size[x];
    get_root (x, -1);
    return root;
}

void dfs(int x)
{
     x = find_root (x);
     f[x] = count (x, 0);
     used[x] = true;
     for (int i = fi[x], t; i != -1; i = e[i].n)
     {
         t = e[i].t;
         if (used[t]) continue;
         f[x] -= count(t, e[i].w);
         dfs (t);
     }
}

int main(void)
{
   // freopen ("1741.in", "r", stdin);
   // freopen ("1741.out", "w", stdout);
    while (scanf ("%d%d", &n, &m) != EOF && n)
    {
          init();
          size[1] = n, dfs (1);
          int ans = 0;
          for (int i = 1; i <= n; i++)
              ans += f[i];
          printf ("%d\n", ans);
    }
    return 0;
}

• 给点数据 (90) lz1 2012-02-05 16:58:55
  • 数据错了 (95) lz1 2012-02-05 17:02:07