思想
一种同时维护点和边的建图方法。
代码
import java.io.*;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = (int)1e5+5, tt=-1, hh=0, cnt=0, ans = 0, n, m;
static boolean[] st1 = new boolean[N]; //标记城市是否被访问
static boolean[] st2 = new boolean[N]; //标记道路是否需要走
static ArrayList<PII>[] g = new ArrayList[N]; //存储城市连接的城市编号和其路径编号
static int[] q = new int[N];
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static void bfs(){
while(hh<=tt){
if(cnt==n) break; //城市都能被访问就结束
int t = q[hh++];
for(PII i : g[t]){
//因为这里需要统计要走的道路,而st2[i.pid]=true表示统计过这条路,就不需要统计了
if(!st1[i.cid] && !st2[i.pid]){
st1[i.cid] = true;
st2[i.pid] = true;
q[++tt] = i.cid;
ans++; //需要走的道路数量
cnt++;
}
}
}
}
public static void main(String[] args)throws IOException{
n = nextInt(); m = nextInt();
for(int i=1; i<=m; i++){
int x = nextInt();
st1[x] = true; //城市x可以警察局访问
q[++tt] = x;
cnt++; //可以连接警察局的城市数量
}
for(int i=1; i<=n; i++) g[i] = new ArrayList<>();
for(int i=1; i<=n-1; i++){
int a = nextInt(), b = nextInt();
g[a].add(new PII(b, i)); g[b].add(new PII(a, i));
}
bfs();
out.println(n-1-ans);
out.flush();
out.close();
}
}
class PII{
int cid; //城市编号
int pid; //城市道路
public PII(int cid, int pid){
this.cid = cid;
this.pid = pid;
}
}