#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define ii pair <int, int>
#define fi first
#define se second
const int N = 2e5 + 10;
int n, m, k, x, y;
int par[N], dp[N];
int num, a[N], tim, in[N], out[N];
int depth[N], up[N][20], Log2[N];
vector <ii> v[N];
vector <int> ans;
bool ck[N];
void DFS(int s = 1, int p = -1) {
in[s] = out[s] = ++tim;
for (ii z: v[s]) {
if (z.se == p) continue;
par[z.se] = s;
depth[z.se] = depth[s] + 1;
up[z.se][0] = s;
for (int i = 1; i <= Log2[depth[z.se]]; ++i) {
up[z.se][i] = up[up[z.se][i - 1]][i - 1];
}
DFS(z.se, s);
out[s] = out[z.se];
}
}
int LCA(int A, int B) {
if (depth[A] < depth[B]) swap(A, B);
int step = depth[A] - depth[B];
for (int i = 0; i <= Log2[step]; ++i) {
if (step >> i & 1) A = up[A][i];
}
if (A == B) return A;
for (int i = Log2[depth[A]]; i >= 0; --i) {
if (up[A][i] != up[B][i]) {
A = up[A][i];
B = up[B][i];
}
}
return up[A][0];
}
struct BIT {
int val[N];
void update(int u, int V) {
while (u <= n) {
val[u] += V;
u += u & -u;
}
}
int get(int u) {
int res = 0;
while (u > 0) {
res += val[u];
u -= u & -u;
}
return res;
}
int range(int l, int r) {
return get(r) - get(l - 1);
}
} bit;
void Path(int &A, int B) {
int l = LCA(A, B);
if (l != A) {
++dp[A]; ++dp[B];
dp[l] -= 2;
A = l;
} else {
if (bit.range(in[B], out[B]) == 0) {
--dp[A]; ++dp[B];
}
}
}
bool cmp(const int &A, const int &B) {
return in[A] < in[B];
}
void dodp(int s = 1, int la = -1) {
for (ii z: v[s]) {
if (z.fi == la) continue;
dodp(z.se, z.fi);
dp[s] += dp[z.se];
}
if (dp[s] >= k) ans.push_back(la);
}
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 1; i < n; ++i) {
cin >> x >> y;
v[x].push_back(ii(i, y));
v[y].push_back(ii(i, x));
if (i >= 2) Log2[i] = Log2[i >> 1] + 1;
}
DFS();
while (m--) {
cin >> num;
for (int i = 1; i <= num; ++i) cin >> a[i];
sort(a + 1, a + num + 1, cmp);
int cur = a[1];
bit.update(in[a[1]], 1);
for (int i = 2; i <= num; ++i) {
Path(cur, a[i]);
bit.update(in[a[i]], 1);
}
for (int i = 1; i <= num; ++i) {
bit.update(in[a[i]], -1);
}
}
dodp();
cout << ans.size() << "\n";
for (int z: ans) cout << z << " ";
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... |