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);
}
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);
}
