TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5747
  • Problem
  • P5747打针
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,128
    Description

     NK信竞队有n名同学和对应n张电脑桌。
     信竞队专用教室布局特别,n张电脑桌通过n-1条走道连接起来,每条走道都有一定的长度,任意两张电脑桌都可相互到达,形成一棵树形。
     同学们正在各自的电脑桌前写代码。何老板走进教室,说道“请同学们都到1号电脑桌来打针,预防脑残病毒。”
     同学们一听要打针,纷纷逃离,躲到电脑桌下瑟瑟发抖。这让何老板很是恼火。
     何老板发现,学生们只会往远离1号电脑桌的方向逃跑。因为担心离开自己电脑太远,会被其他同学机惨,所以他们只会在距离自己的电脑桌不会超过K米的桌子下躲藏。
     何老板想知道,位于i号电脑桌的同学,他有多少个藏身处。

    Input Format

    第一行,两个整数n和k
    接下来n-1行,每行两个整数X和L,描述一条走道。
    其中第i行的x表示编号i的电脑桌到1号电脑桌的路线上,离它最近那张电脑桌的编号(即i的父亲节点的编号x,1<=x<i),L表示i号电脑桌与x号电脑桌之间的走道的长度。

    Output Format

    n行,每行一个整数,其中第i行表示位于i号电脑桌的同学的藏身处的个数。

    Sample Input 1

    4 5 
    1 4 
    2 3 
    1 5 

    Sample Output 1




    1

    Sample Input 2

    10 48
    1 57
    2 29
    2 33
    4 1
    3 49
    1 33
    2 53
    7 53
    4 41

    Sample Output 2

    2
    4
    1
    3
    1
    1
    1
    1
    1
    1

    Hint

    $1 <= n <= 200,000$
    $1 <= k <= 10^{18}$
    $1 <= L <= 10^{12}$

    样例1说明:
    2号桌与1号桌相连,走道长度为4
    3号桌与2号桌相连,走道长度为3
    4号桌与1号桌相连,走道长度为5
    位于1号桌的同学,可藏身到1,2,4号桌
    位于2号桌的同学,可藏身到2,3号桌
    位于3,4号桌的同学,只能藏身到自己的电脑桌下