// source problem :
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
const int inf = 1e18;
void ckmax(int& f, int s)
{
f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
f = (f < s ? f : s);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<pair<int, int>>> adj(n);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
adj[--u].emplace_back(--v, i - 1);
adj[v].emplace_back(u, i - 1);
}
vector<vector<int>> q(n);
vector<int> cnt(m);
for (int i = 0; i < m; i++)
{
int a;
cin >> a;
cnt[i] = a;
while (a--)
{
int x;
cin >> x;
q[--x].push_back(i);
}
}
vector<int> ans(n - 1);
function<void(int, int, map<int, int>&)> dfs = [&](int u, int p, map<int, int>& mp)
{
for (int i : q[u]) mp[i]++;
for (auto [v, id] : adj[u])
{
if (v == p) continue;
map<int, int> cmp;
dfs(v, u, cmp);
ans[id] += cmp.size();
if (cmp.size() > mp.size())
{
for (auto [f, s] : mp)
{
cmp[f] += s;
if (cmp[f] == cnt[f]) cmp.erase(f);
}
swap(mp, cmp);
}
else
{
for (auto [f, s] : cmp)
{
mp[f] += s;
if (mp[f] == cnt[f]) mp.erase(f);
}
}
}
};
map<int, int> mp;
dfs(0, -1, mp);
cout << count_if(all(ans), [&](int i){return i >= k;}) << '\n';
for (int i = 0; i < n - 1; i++)
{
if (ans[i] >= k) cout << i + 1 << ' ';
}
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... |