Railways

ThegeekKnight16

Jun 14th, 2023

1,130

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.15 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 21;
array<vector<pair<int, int> >, MAXN> grafo;
array<int, MAXN> prof, tin, marcVert;
array<pair<int, int>, MAXN> pai;
int dp[MAXN][MAXK];
int temp = 0;
void dfs(int v, int p, int edge)
{
prof[v] = prof[p]+1; tin[v] = ++temp;
dp[v][0] = p;
for (int k = 1; k < MAXK; k++) dp[ dp[v][k-1] ][k-1];
pai[v] = make_pair(p, edge);
for (auto [viz, e] : grafo[v])
{
if (viz == p) continue;
dfs(viz, v, e);
}
}
int lca(int a, int b)
{
if (prof[a] < prof[b]) swap(a, b);
int D = prof[a] - prof[b];
for (int k = 0; k < MAXK; k++) if (D & (1 << k)) a = dp[a][k];
if (a == b) return a;
for (int k = MAXK-1; k >= 0; k--)
{
if (dp[a][k] != dp[b][k])
{
a = dp[a][k];
b = dp[b][k];
}
}
return dp[a][0];
}
void solveMarc(int v, int p)
{
for (auto [viz, e] : grafo[v])
{
if (viz == p) continue;
solveMarc(viz, v);
marcVert[v] += marcVert[viz];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
for (int i = 1; i < N; i++)
{
int X, Y;
cin >> X >> Y;
grafo[X].emplace_back(Y, i);
grafo[Y].emplace_back(X, i);
}
dfs(1, 1, -1);
for (int i = 1; i <= M; i++)
{
int S;
cin >> S;
vector<int> verts(S);
for (auto &x : verts) cin >> x;
sort(verts.begin(), verts.end(), [&](const int &a, const int &b) {return tin[a] < tin[b];});
verts.push_back(verts[0]);
for (int i = 0; i < verts.size()-1; i++)
{
marcVert[verts[i]]++; marcVert[verts[(i+1)]]++;
marcVert[lca(verts[i], verts[(i+1)])] -= 2;
}
}
solveMarc(1, 1);
vector<int> resp;
for (int i = 2; i <= N; i++) if (marcVert[i] >= 2*K) resp.push_back(pai[i].second);
sort(resp.begin(), resp.end());
cout << resp.size() << '\n';
for (auto x : resp) cout << x << " ";
cout << '\n';
}

Add Comment

Please, Sign In to add comment