#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Anton is nigga
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstring> // Для memset
using namespace std;
typedef long long ll;
typedef long double ld;
typedef std::pair <ll, ll> pii;
typedef std::pair <ld, ld> pdd;
const ll DIM = 100007;
const ll MXMASK = (1 << 20);
const ll INF = 1e18;
const ll mod = 1000000007;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const char endL = '\n';
const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };
FILE* stream;
int n, m, k;
vector < pair < int, int > > v[DIM];
int timer;
int euler[DIM], tin[DIM], tout[DIM], heavy[DIM], weight[DIM], depth[DIM];
vector < int > colors[DIM];
vector < int > res;
void precount(int val, int prev, int dep) {
tin[val] = ++timer;
euler[timer] = val;
depth[val] = dep;
weight[val] = 1;
for (auto e : v[val]) {
int to = e.first;
if (to == prev) continue;
precount(to, val, dep + 1);
weight[val] += weight[to];
}
tout[val] = timer;
}
int cnt[DIM], fullColor[DIM];
int ans;
void add(int col) {
if (cnt[col] == 0) ans++;
cnt[col]++;
if (cnt[col] == fullColor[col]) ans--;
}
void del(int col) {
if (cnt[col] == fullColor[col]) ans++;
cnt[col]--;
if (cnt[col] == 0) ans--;
}
void solve(int val, int prev, bool heavyStat) {
int heavy = 0, heavyE = 0;
for (auto e : v[val]) {
int to = e.first, num = e.second;
if (num == prev) continue;
if (weight[to] > weight[heavy]) {
heavy = to;
heavyE = num;
}
}
for (auto e : v[val]) {
int to = e.first, num = e.second;
if (to != heavy && num != prev) {
solve(to, num, false);
}
}
if (heavy != 0) {
solve(heavy, heavyE, true);
}
for (auto e : v[val]) {
int to = e.first, num = e.second;
if (to != heavy && num != prev) {
for (int i = tin[to]; i <= tout[to]; i++) {
for (auto x : colors[euler[i]]) {
add(x);
}
}
}
}
for (auto x : colors[val]) {
add(x);
}
if (ans >= k && prev != -1) res.push_back(prev);
if (!heavyStat) {
for (int i = tin[val]; i <= tout[val]; i++) {
for (auto x : colors[euler[i]]) {
del(x);
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
//freopen_s(&stream, "input.txt", "r", stdin);
//freopen_s(&stream, "output.txt", "w", stdout);
cin >> n >> m >> k;
for (int i = 1; i < n; i++) {
int v1, v2;
cin >> v1 >> v2;
v[v1].push_back({ v2, i });
v[v2].push_back({ v1, i });
}
precount(1, 1, 1);
for (int i = 1; i <= m; i++) {
int x;
cin >> fullColor[i];
for (int j = 1; j <= fullColor[i]; j++) {
cin >> x;
colors[x].push_back(i);
}
}
solve(1, -1, true);
cout << res.size() << endl;
for (auto x : res) cout << x << " ";
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... |