#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const int MAXN = 100'005;
int n, m, k;
// trying out maxn just to see the speed increase
vector<pair<int,int>> adj[MAXN];
int p[20][MAXN], depth[MAXN], tin[MAXN], tout[MAXN], timer, pedge[MAXN];
ll diff[MAXN], ecnt[MAXN];
void dfs(int u, int rt, int pe) {
p[0][u] = rt;
pedge[u] = pe;
tin[u] = ++timer;
for (auto [v, id] : adj[u]) {
if (v == rt) continue;
depth[v] = depth[u] + 1;
dfs(v, u, id);
}
tout[u] = timer;
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int i = 19; i >= 0; i--)
if (p[i][a] && depth[p[i][a]] >= depth[b])
a = p[i][a];
if (a == b) return a;
for (int i = 19; i >= 0; i--)
if (p[i][a] && p[i][a] != p[i][b]) {
a = p[i][a];
b = p[i][b];
}
return p[0][a];
}
void dfs2(int u, int rt) {
for (auto [v, id] : adj[u]) {
if (v == rt) continue;
dfs2(v, u);
diff[u] += diff[v];
ecnt[id] = diff[v];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
for (int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
dfs(1, 0, 0);
for (int i = 1; i < 20; i++)
for (int v = 1; v <= n; v++)
p[i][v] = p[i - 1][p[i - 1][v]];
while (m--) {
int s;
cin >> s;
vector<int> nodes(s);
for (int i = 0; i < s; i++) cin >> nodes[i];
sort(nodes.begin(), nodes.end(), [&](int a, int b) { return tin[a] < tin[b]; });
vector<int> vt = nodes;
for (int i = 0; i + 1 < nodes.size(); i++)
vt.push_back(lca(nodes[i], nodes[i + 1]));
sort(vt.begin(), vt.end(), [&](int a, int b) { return tin[a] < tin[b]; });
vt.erase(unique(vt.begin(), vt.end()), vt.end());
stack<int> st;
st.push(vt[0]);
for (int i = 1; i < vt.size(); i++) {
int u = vt[i];
while (!st.empty() &&
!(tin[st.top()] <= tin[u] && tin[u] <= tout[st.top()]))
st.pop();
int v = st.top(), w = lca(u, v);
diff[u]++;
diff[v]++;
diff[w] -= 2;
st.push(u);
}
}
dfs2(1, 0);
vector<int> ans;
for (int i = 1; i <= n - 1; i++)
if (ecnt[i] >= k)
ans.push_back(i);
cout << ans.size() << '\n';
for (int x : ans) cout << x << ' ';
cout << '\n';
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |