All Tracks Algorithms Graphs Graph Representation Problem

Coloring trees
Tag(s):

Algorithms, Graphs

Problem
Editorial
Analytics

There are \(N\) cities that are connected by \(N-1\) roads. \(K\) cities have bus terminals and other \(N-K\) cities have bus stops. A bus terminus is a designated place where a bus starts or ends its scheduled route.

A bus should start from a terminal and must end its journey at another terminal visiting any city at most once. A city is crowded if there is a bus service in the city where one or more than one bus visits it along any route. You are required to simulate the routes for the buses so that the maximum number of cities is crowded. You can assume there is a number of buses ready for service from each terminus.

Note:

  • A city with a bus terminal is always crowded.
  • It is guaranteed that it is possible to reach from one city to another city.

Input format

  • First line: Two space-separated integers \(N\) and \(K\)
  • Next \(N-1\) lines: Two integers \(u\) and \(v\) that denote city \(u\) and city \(v\) is connected by a road
  • Next line: \(K\) integers denoting the cities that have a bus terminal

Output format

Print the number of cities that are crowded after all simulations. 

Constraints

\(1 \leq N \leq 200000\)

\(1 \leq K, u, v \leq N\)

It is guaranteed that it is possible to reach from one city to another city.

SAMPLE INPUT
5 3
1 2
1 3
2 4
2 5
1 4 5
SAMPLE OUTPUT
4
Explanation

It is possible to simulate a bus route starting from terminus 1 to terminus 4 or 5 thereby making city 2, a crowded city. But it is impossible to make city 3 crowded.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Circuits '19

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?