import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;
@SuppressWarnings("unchecked")
public class g implements Runnable {
int n, m;
boolean[] active;
ArrayList<Integer>[] vs;
boolean go(int dist) {
int[] deg = new int[n];
ArrayDeque<Integer> q = new ArrayDeque<Integer>();
for(int i = 0; i < n; ++i) {
deg[i] = vs[i].size();
if(deg[i] == 1) q.add(i);
}
int placed = 0;
while(!q.isEmpty()) {
//remove stupid leafs
ArrayDeque<Integer> nq = new ArrayDeque<>();
while(!q.isEmpty()) {
int node = q.poll();
if(!active[node]) {
deg[node]--;
for(int v : vs[node]) {
if(--deg[v] == 1) {
q.add(node);
}
}
} else {
nq.add(node);
}
}
q = nq;
int prevSize = 0;
for(int iter = 0; iter < dist && !q.isEmpty(); ++iter) {
prevSize = q.size();
nq = new ArrayDeque<>();
while(!q.isEmpty()) {
int node = q.poll();
deg[node]--;
for(int v : vs[node]) {
if(--deg[v] == 1) {
nq.add(node);
}
}
}
q = nq;
}
//we have all nodes where we need to place stuff
if(q.isEmpty()) placed += prevSize;
placed += q.size();
for(int iter = 0; iter <= dist && !q.isEmpty(); ++iter) {
nq = new ArrayDeque<>();
while(!q.isEmpty()) {
int node = q.poll();
deg[node]--;
for(int v : vs[node]) {
if(--deg[v] == 1) {
nq.add(node);
}
}
}
q = nq;
}
}
return placed <= m;
}
public void solve(FS in, PrintWriter out) {
n = in.nextInt();
m = in.nextInt();
active = new boolean[n];
vs = new ArrayList[n];
for(int i = 0; i < n; ++i) {
active[i] = in.nextInt() == 1;
vs[i] = new ArrayList<>();
}
for(int i = 0; i < n - 1; ++i) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
vs[u].add(v);
vs[v].add(u);
}
int lo = 0, hi = n;
while(lo <= hi) {
int mid = lo + hi >> 1;
boolean works = go(mid);
if(works) hi = mid - 1;
else lo = mid + 1;
}
out.println(lo);
}
public void run() {
FS in = new FS();
PrintWriter out = new PrintWriter(System.out);
solve(in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, new g(), "lmao", 1L<<28).start();
}
static class FS {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while(!st.hasMoreElements()) {
try { st = new StringTokenizer(br.readLine()); }
catch(Exception e) {}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
Compilation message
dyn.java:9: error: class g is public, should be declared in a file named g.java
public class g implements Runnable {
^
1 error
