In this HackerEarth Coloring trees problem solution There are N cities that are connected by N – 1 road. 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.
HackerEarth Coloring trees problem solution.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;
import java.util.TreeSet;
import java.io.InputStream;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
ColoringTheTree solver = new ColoringTheTree();
int testCount = 1;
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
static class ColoringTheTree {
PrintWriter out;
InputReader in;
public void solve(int testNumber, InputReader in, PrintWriter out) {
this.out = out;
this.in = in;
int n = ni();
int k = ni();
TreeSet<Integer>[] tree = new TreeSet[n];
int i = 0;
for (i = 0; i < n; i++)
tree[i] = new TreeSet<>();
int[] deg = new int[n];
for (i = 0; i < n - 1; i++) {
int u = ni() - 1;
int v = ni() - 1;
tree[u].add(v);
tree[v].add(u);
deg[u]++;
deg[v]++;
}
boolean[] is_terminus = new boolean[n];
for (i = 0; i < k; i++)
is_terminus[ni() - 1] = true;
Queue<Integer> qu = new LinkedList<>();
for (i = 0; i < n; i++) {
if (!is_terminus[i] && deg[i] == 1)
qu.add(i);
}
int not_visited = 0;
while (qu.size() > 0) {
int curr = qu.poll();
for (int u : tree[curr]) {
tree[u].remove(curr);
deg[u]--;
}
for (int u : tree[curr]) {
if (deg[u] == 1 && !is_terminus[u])
qu.add(u);
}
not_visited++;
}
pn(n - not_visited);
}
int ni() {
return in.nextInt();
}
void pn(long zx) {
out.println(zx);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new UnknownError();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new UnknownError();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int nextInt() {
return Integer.parseInt(next());
}
public String next() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
private boolean isSpaceChar(int c) {
return c == ' ' || c == 'n' || c == 'r' || c == 't' || c == -1;
}
}
}