TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7344
  • 题目
  • P7344雨天的尾巴
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    N个点,形成一个树状结构。有M次发放,每次选择两个点x,y 对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成 所有发放后,每个点存放最多的是哪种物品。

    输入格式

    第一行数字N,M 接下来N-1行,每行两个数字a,b,表示a与b间有一条边 再接下来M行,每行三个数字x,y,z.如题

    输出格式

    输出有N行 每i行的数字表示第i个点存放最多的物品是哪一种,如果有 多种物品的数量一样,输出编号最小的。如果某个点没有物品 则输出0

    样例输入

    20 50
    8 6
    10 6
    18 6
    20 10
    7 20
    2 18
    19 8
    1 6
    14 20
    16 10
    13 19
    3 14
    17 18
    11 19
    4 11
    15 14
    5 18
    9 10
    12 15
    11 14 87
    12 1 87
    14 3 84
    17 2 36
    6 5 93
    17 6 87
    10 14 93
    5 16 78
    6 15 93
    15 5 16
    11 8 50
    17 19 50
    5 4 87
    15 20 78
    1 17 50
    20 13 87
    7 15 22
    16 11 94
    19 8 87
    18 3 93
    13 13 87
    2 1 87
    2 6 22
    5 20 84
    10 12 93
    18 12 87
    16 10 93
    8 17 93
    14 7 36
    7 4 22
    5 9 87
    13 10 16
    20 11 50
    9 16 84
    10 17 16
    19 6 87
    12 2 36
    20 9 94
    9 2 84
    14 1 94
    5 5 94
    8 17 16
    12 8 36
    20 17 78
    12 18 50
    16 8 94
    2 19 36
    10 18 36
    14 19 50
    4 12 50

    样例输出

    87
    36
    84
    22
    87
    87
    22
    50
    84
    87
    50
    36
    87
    93
    36
    94
    16
    87
    50
    50

    提示

    1<=N,M<=100000
    1<=a,b,x,y<=N
    1<=z<=10^9