TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3329
  • 問題
  • P3329race
    制限 : 時間制限 : 60000 MS   メモリ制限 : 265536 KB
    問題説明

    In conjunction with the IOI, Pattaya City will host a race: the International Olympiad in Racing
    (IOR) 2011. As the host, we have to find the best possible course for the race.
    In the Pattaya-Chonburi metropolitan area, there are N cities connected by a network of N-1
    highways. Each highway is bidirectional, connects two different cities, and has an integer length
    in kilometers. Furthermore, there is exactly one possible path connecting any pair of cities. That
    is, there is exactly one way to travel from one city to another city by a sequence of highways
    without visiting any city twice.
    The IOR has specific regulations that require the course to be a path whose total length is exactly
    K kilometers, starting and ending in different cities. Obviously, no highway (and therefore also
    no city) may be used twice on the course to prevent collisions. To minimize traffic disruption, the
    course must contain as few highways as possible.
    Your task
    Write a procedure best_path(N,K,H,L) that takes the following parameters:
    • N– the number of cities. The cities are numbered 0 through N-1.
    • K – the required distance for the race course.
    • H– a two-dimensional array representing highways. For 0 ≤ i < N-1, highway i connects
    the cities H[i][0] and H[i][1].
    • L – a one-dimensional array representing the lengths of the highways. For 0 ≤ i < N-1,
    the length of highway i is L[i].
    You may assume that all values in the array H are between 0 and N-1, inclusive, and that the
    highways described by this array connect all cities as described above. You may also assume that
    all values in the array L are integers between 0 and 1 000 000, inclusive.
    Your procedure must return the minimum number of highways on a valid race course of length
    exactly K. If there is no such course, your procedure must return -1.

    给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.

    入力形式

    Line 1: N and K.
    • Lines 2 to N: information on the highways; i.e., line i+2 contains H[i][0], H[i][1],
    and L[i], separated by a space, for 0 ≤ i < N-1.

    第一行 两个整数 n, k
    第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

    出力形式

    the expected solution.

    一个整数 表示最小边数量 如果不存在这样的路径 输出-1

    サンプル入力

    4 3
    0 1 1
    1 2 2
    1 3 4

    サンプル出力

    2

    ヒント

    1 <= N <= 200000
    1 <= K <= 1000000


    ソース  ioi 2011