| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 878199 | vjudge1 | Railway (BOI17_railway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
const int LG = 18;
int n, m, k;
int n1[N], n2[N], par[N][LG], h[N], tm[N], ps[N], t;
vector<int> edj[N], ans;
void dfs_pre(int v = 1, int p = 0) {
tm[v] = t++, h[v] = h[p] + 1;
par[v][0] = p;
for (int lg = 1; lg < LG; lg++)
par[v][lg] = par[par[v][lg - 1]][lg - 1];
for (auto e : edj[v]) {
int u = n1[e] ^ n2[e] ^ v;
if (u ^ p) dfs_pre(u, v);
}
}
int lca(int u, int v) {
if (h[u] > h[v]) swap(u, v);
int dist = h[v] - h[u];
for (int lg = 0; lg < LG; lg++)
if (dist & (1 << lg)) v = par[v][lg];
if (u == v) return v;
for (int lg = LG - 1; lg >= 0; lg--)
if (par[v][lg] ^ par[u][lg])
v = par[v][lg], u = par[u][lg];
return par[v][0];
}
void dfs(int v = 1, int p = -1) {
for (auto e : edj[v])
if (e ^ p) {
int u = n1[e] ^ n2[e] ^ v;
dfs(u, e);
ps[v] += ps[u];
}
if (ps[v] >= k) ans.pb(p);
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < n - 1; i++) {
cin >> n1[i] >> n2[i];
edj[n1[i]].pb(i);
edj[n2[i]].pb(i);
}
dfs_pre();
while (m--) {
int x;
cin >> x;
vector<int> vec(x);
for (int i = 0; i < x; i++) cin >> vec[i];
sort(vec.begin(), vec.end(), [](int p, int q) {return tm[p] < tm[q];});
vec.pb(vec[0]);
for (int i = 0; i < x; i++)
ps[vec[i + 1]]++, ps[lca(vec[i], vec[i + 1])] -= 1;
}
dfs();
cout << ans.size() << '\n';
for (auto e : ans) cout << e + 1 << ' ';
cout << '\n';
return 0;
}