Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.77 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5. import java.util.ArrayList;
  6. //https://pastebin.com/vaXQ31LR
  7. public class ccc16s3 {
  8. static int n, k, ans, max = 0, p;
  9. static boolean good[] = new boolean[200005];
  10. static ArrayList<Integer> adj[] = new ArrayList[200005];
  11. static void dfs(int N, int P){
  12. for (int l = 0; l < adj[N].size(); ++l){
  13. int next = adj[N].get(l);
  14. if (next == P) continue;
  15. dfs(next, N);
  16. good[N] |= good[next];
  17. if (good[next]) ans ++;
  18. }
  19. }
  20. static void get_dis(int N, int P, int D){
  21. if (!good[N]) return;
  22. for (int l = 0; l < adj[N].size(); ++l){
  23. int next = adj[N].get(l);
  24. if (next == P) continue;
  25. get_dis(next, N, D + 1);
  26. }
  27. if (D > max){
  28. p = N;
  29. max = D;
  30. }
  31. }
  32. public static void main(String[] args)
  33. {
  34. FastReader in = new FastReader();
  35. n = in.nextInt(); k = in.nextInt();
  36. for (int l = 0; l <= n; ++ l){
  37. adj[l] = new ArrayList<Integer>();
  38. }
  39. int a = 0;
  40. for (int l = 0; l < k; ++l){
  41. a = in.nextInt();
  42. good[a] = true;
  43. }
  44. int start = a;
  45. for (int l = 0; l < n - 1; ++l){
  46. a = in.nextInt(); int b = in.nextInt();
  47. adj[a].add(b);
  48. adj[b].add(a);
  49. }
  50. dfs(start, -1);
  51. get_dis(start, -1, 0);
  52. get_dis(p, -1, 0);
  53. //System.out.println(max);
  54. System.out.println(ans * 2 - max);
  55. }
  56. static class FastReader {
  57. BufferedReader br;
  58. StringTokenizer st;
  59. public FastReader(){
  60. br = new BufferedReader(new
  61. InputStreamReader(System.in));
  62. }
  63. String next(){
  64. while (st == null || !st.hasMoreElements()){
  65. try {
  66. st = new StringTokenizer(br.readLine());
  67. }
  68. catch (IOException e) {
  69. e.printStackTrace();
  70. }
  71. }
  72. return st.nextToken();
  73. }
  74. int nextInt()
  75. {
  76. return Integer.parseInt(next());
  77. }
  78. long nextLong()
  79. {
  80. return Long.parseLong(next());
  81. }
  82. double nextDouble()
  83. {
  84. return Double.parseDouble(next());
  85. }
  86. String nextLine() {
  87. String str = "";
  88. try {
  89. str = br.readLine();
  90. }
  91. catch (IOException e) {
  92. e.printStackTrace();
  93. }
  94. return str;
  95. }
  96. }
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement