#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
#define ar array
#define mrand(a, b) uniform_int_distribution<int>(a, b)(rng)
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace FAST {
template<typename T, typename F>
istream &operator>>(istream &cin, pair<T, F> &p) {
cin >> p.first >> p.second;
return cin;
}
template<typename T, typename F>
ostream &operator<<(ostream &cout, pair<T, F> &p) {
cout << p.first << ' ' << p.second;
return cout;
}
template<typename T>
istream &operator>>(istream &cin, vector<T> &a) {
for (T &i: a) cin >> i;
return cin;
}
template<typename T>
ostream &operator<<(ostream &cout, vector<T> &a) {
for (T i: a) cout << i << ' ';
return cout;
}
template<typename T>
istream &operator>>(istream &cin, deque<T> &a) {
for (T &i: a) cin >> i;
return cin;
}
template<typename T>
ostream &operator<<(ostream &cout, deque<T> &a) {
for (T i: a) cout << i << ' ';
return cout;
}
}
using namespace FAST;
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;
int binpow(int a, int b, int m){
if(b == 0)return 1;
if(b % 2 == 0){
int c = binpow(a,b/2,m);
return (c*c)%m;
}
return (binpow(a,b-1,m)*a)%m;
}
int divi(int a, int b, int m){
return (a*(binpow(b,m-2, m)))%m;
}
struct Bit {
vector<int> b, b2;
int n;
Bit(int n) {
this->n = n + 1;
b.assign(n + 1, 0);
b2.assign(n+1, 0);
}
void add(vector<int>&b, int idx, int x){
while(idx <= n){
b[idx] += x;
idx += idx & -idx;
}
}
void update(int l, int r, int x){
add(b, l, x);
add(b, r+1, -x);
add(b2, l, x*(l-1));
add(b2, r+1, -x*r);
}
int sum(vector<int>&b, int idx){
int res = 0;
while(idx > 0){
res += b[idx];
idx -= idx & -idx;
}
return res;
}
int pref(int idx){
return sum(b, idx) * idx - sum(b2, idx);
}
int get(int l, int r){
return pref(r) - pref(l-1);
}
};
int n,m,k;
int timer;
int op[N][21];
vector<int>g[N], tin(N), tout(N);
vector<int>sz(N), baty(N);
ste<int>s[N];
ste<int>s2[N];
map<ar<int,2>, int> res, ind;
void dfs(int x, int pr){
op[x][0] = pr;
for(int i = 1;i<=20;i++){
op[x][i] = op[op[x][i-1]][i-1];
}
tin[x] = timer++;
for(auto to:g[x]){
if(to == pr)continue;
dfs(to, x);
}
tout[x] = timer++;
}
bool isbaty(int a, int b){
return (tin[a] < tin[b] && tout[b] < tout[a]);
}
int lca(int a, int b){
if(isbaty(a, b))return a;
if(isbaty(b, a))return b;
for(int i = 20;i>=0;i--){
if(!isbaty(op[a][i], b))a = op[a][i];
}
return op[a][0];
}
int find_baty(int x){
if(baty[x] == x)return x;
return baty[x] = find_baty(baty[x]);
}
void unin(int a, int b){
a = find_baty(a);
b = find_baty(b);
if(a == b)return;
if(s[a].size() < s[b].size())swap(a, b);
baty[b] = a;
for(auto to:s[b]){
s[a].insert(to);
}
}
void ans(int x, int pr){
for(auto to:g[x]){
if(to == pr)continue;
ans(to, x);
unin(x, to);
}
int a = find_baty(x);
// if(x == 3){
// for(auto to:s[a])cout << to << " ";
// cout << "\n";
// for(auto to:s2[x])cout << to << " ";
// cout << "\n";
// }
for(auto to:s2[x]){
int in = s[a].order_of_key(to);
if(0 <= in && in < s[a].size() && *s[a].find_by_order(in) == to){
s[a].erase(s[a].find_by_order(in));
}
}
if(n <= 10000){
set<int>st;
for(auto to:s[a])st.insert(to);
res[{x, pr}] = st.size();
}
else res[{x, pr}] = s[a].size();
}
void solve(){
cin >> n >> m >> k;
for(int i = 1;i<=n;i++){
baty[i] = i;
}
for(int i = 2;i<=n;i++){
int a,b;
cin >> a >> b;
ind[{a, b}] = i-1;
ind[{b, a}] = i-1;
g[a].pb(b);
g[b].pb(a);
}
dfs(1, 1);
// cout << isbaty(3, 6) << "\n";
// cout << op[6][1] << "\n";
for(int i = 1;i<=m;i++){
int a;
cin >> a;
int last = -1;
for(int j = 1;j<=a;j++){
int b;
cin >> b;
if(last > -1){
int u = lca(last, b);
if(u != last)
s[last].insert(i);
if(u != b)
s[b].insert(i);
s2[u].insert(i);
if(u != last && u != b)s2[u].insert(i);
}
last = b;
}
// cout << "\n";
}
// for(auto to:s[3])cout << to << " ";
// cout << "\n";
ans(1, -1);
vector<int>opp;
for(auto to:res){
if(to.second >= k){
if(ind[to.first] == 0)continue;
opp.pb(ind[to.first]);
}
// cout << to.first[0] << " " << to.first[1] << " " << to.second << "\n";
}
sort(all(opp));
cout << opp.size() << "\n";
cout << opp << "\n";
}
/*
*/
signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt=1; //cin >> tt;
while(tt--)solve();
}
# | 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... |