TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2755
  • 問題
  • P2755树的统计1
    制限 : 時間制限 : 20000 MS   メモリ制限 : 262144 KB
    審判説明 : 2s,256MB
    問題説明

    给一棵每条边带权的无根树,定义节点x与y之间的距离dis(x,y)为从x到y的唯一路径上的边权之和。
    你需要求出dis(x,y)<=K的点对(x,y)的数量,其中x<y。

    入力形式

    有多组测试数据
    每组测试数据第一行为两个整数N,K,当N=K=0时输入文件结束。
    接下来N-1行每行三个整数x,y,z,表示节点x,y之间有一条权值为z的边。

    出力形式

    每组数据输出一行,为一个整数,距离不超过K的点对(x,y)的个数。

    サンプル入力

    5 4
    1 2 3
    1 3 1
    1 4 2
    3 5 1
    0 0

    サンプル出力

    8

    ヒント

    1<=N<=30000
    1<=K<=109
    1<=x,y<=N
    0<=z<=5000
    测试数据不超过10组。


    ソース  POJ1741,感谢nodgd翻译并提供数据