fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector< vector<int> > G;
  6. vector<char> isP;
  7. int K;
  8.  
  9. int dfs2(int v, int p, int l){
  10. 	int res = 0;
  11. 	for (auto next : G[v])
  12. 		if (next !=p)
  13. 			res+=dfs2(next,v, l+1);
  14. 	if (isP[v])
  15. 		res+=l;
  16. 	return res;
  17. }
  18.  
  19.  
  20. int dfs(int v, int p){
  21. 	int res = isP[v];
  22. 	for (auto next : G[v])
  23. 		if (next !=p)
  24. 			res+=dfs(next,v);
  25. 	if (res > K/2){
  26. 		cout << dfs2(v,-1,0)<<" "<<v<<endl;
  27. 		exit(0);
  28. 	}
  29. 	return res;
  30. }
  31.  
  32. int main() {
  33. 	// your code goes here
  34. 	int N;
  35. 	cin >> N >> K;
  36. 	G.resize(N);
  37. 	isP.resize(N);
  38. 	for (int _=1; _ < N; _++){
  39. 		int a,b;
  40. 		cin >> a >> b;
  41. 		a--;
  42. 		b--;
  43. 		G[a].push_back(b);
  44. 		G[b].push_back(a);
  45. 	}
  46. 	for (int _ = 0; _ < K; _++){
  47. 		int a;
  48. 		cin >> a;
  49. 		isP[a-1] = 1;
  50. 	}
  51. 	dfs(0,-1);
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
8 4


1 2
1 3
1 4
4 6
4 5
5 7
5 8

2 5 6 7
stdout
copy 
6 3
https://ideone.com/eIbkNs
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!