This page is still under construction.

Parts of this page are still being built. What you see may change.

Chicken Joggers

Time limit1sMemory limit256 MB

Summary
Place the fewest extra lamps so every trail a jogger who starts at intersection 1 and returns after exactly S meters could use has a lamp on one end.
Level

Medium6 of 10

Topics
Dynamic programming, Tree, DFS
Solved
No attempts yet

Problem

A forest has a network of jogging trails. There are NN intersections and N−1N-1 trails, and between any two intersections there is exactly one route along the trails, so the whole network forms a tree.

Every jogger starts at intersection 1, runs exactly SS meters in total, and finishes back at intersection 1. A jogger can turn around at any point, including the middle of a trail, and can turn around as many times as she wants. Nobody knows which route a jogger takes, so treat every route that meets those conditions as one that might really be run. Running over part of a trail and turning back still counts as using that trail.

The forest is dark at night. The joggers want every trail they might use to be lit. A trail is lit when at least one of its two end intersections has a lamp. LL intersections already have a lamp, and those lamps stay.

Place extra lamps at intersections so that every trail that might be used is lit. Find the smallest number of extra lamps.

Input

The first line has the number of intersections NN and the running distance SS. (2≤N≤500002 \le N \le 50000, 1≤S≤1041 \le S \le 10^4)

Each of the next N−1N-1 lines has three integers aa, bb, dd, meaning a bidirectional trail of length dd meters joins intersections aa and bb. (1≤a,b≤N1 \le a, b \le N, 1≤d≤1001 \le d \le 100)

The next line has LL, the number of intersections that already have a lamp. (0≤L≤N0 \le L \le N)

The line after that has the LL intersection numbers that have a lamp, separated by spaces. The numbers are all different. When LL is 00 the line is empty.

Output

Print the smallest number of extra lamps on one line.

Examples3

  1. Example 1

    Input
    5 6
    1 2 1
    1 3 1
    4 3 3
    3 5 2
    1
    1
    
    Expected output
    1
    
  2. Example 2

    Input
    5 6
    1 2 1
    1 3 1
    4 3 3
    3 5 2
    1
    3
    
    Expected output
    1
    
  3. Example 3

    Input
    5 6
    1 3 3
    1 4 2
    1 5 3
    1 2 2
    2
    4 3
    
    Expected output
    1