Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 – Elimination Round 3), problem: (F) Santa Clauses and a Soccer Championship Solution in C/C++

Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 – Elimination Round 3), problem: (F) Santa Clauses and a Soccer Championship Solution in C/C++

 

 

#include <bits/stdc++.h>

using namespace std;

vector<int> g[200005], lst[2];

int n, k, c, s[200005], p;
bool f[200005];

void dfs(int x, int fa = -1) {
	if(f[x]) 
		lst[++c > k].push_back(x);
	for(auto y: g[x]) {
		if(y == fa) continue;
		dfs(y, x);
		s[x] += s[y];
		if(s[x] >= k and !p) p = x;
	}
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1;i < n;i++) {
		int a, b; scanf("%d%d", &a, &b);
		g[a].push_back(b), g[b].push_back(a);
	}
	for(int i = 0;i < 2 * k;i++) {
		int x; scanf("%d", &x);
		f[x] = true; s[x] = 1;
	}
	dfs(1);
	printf("1\n%d\n", p);
	for(int i = 0;i < k;i++)
			printf("%d %d %d\n", lst[0][i], lst[1][i], p);
}