This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
struct node_t {
vector<int> anc, childs;
int depth, tin, tout, parrid;
};
vector<vector<pair<int, int>>> adj;
vector<node_t> tree;
vector<int> st;
int t = 0;
void buildTree(int cur) {
tree[cur].tin = t;
t++;
for (auto& p : adj[cur]) {
if (not tree[cur].anc.empty() and tree[cur].anc[0] == p.first) continue;
tree[p.first].anc.push_back(cur);
tree[p.first].parrid = p.second;
tree[cur].childs.push_back(p.first);
tree[p.first].depth = tree[cur].depth + 1;
buildTree(p.first);
}
tree[cur].tout = t;
t++;
}
void buildAnc(int cur) {
int id = tree[cur].anc[0], step = 0;
while (tree[id].anc.size() >= step + 1) {
id = tree[id].anc[step];
tree[cur].anc.push_back(id);
step++;
}
for (int child : tree[cur].childs) buildAnc(child);
}
int findLCA(int a, int b) {
if (tree[a].depth > tree[b].depth) swap(a, b);
if (a == 1) return 1;
int pos = tree[b].anc.size() - 1;
while (tree[b].depth > tree[a].depth) {
while (pos >= tree[b].anc.size() or tree[tree[b].anc[pos]].depth < tree[a].depth) pos--;
b = tree[b].anc[pos];
}
if (a == b) return a;
pos = tree[a].anc.size() - 1;
while (true) {
while (pos >= 0 and (pos >= tree[a].anc.size() or tree[a].anc[pos] == tree[b].anc[pos])) pos--;
if (pos < 0) break;
a = tree[a].anc[pos];
b = tree[b].anc[pos];
}
return tree[a].anc[0];
}
int que(int id, int l, int r, int ql, int qr) {
if (l > qr or r < ql) return 0;
if (ql <= l and r <= qr) return st[id];
int mid = (l + r) / 2;
return que(lid, l, mid, ql, qr) + que(rid, mid + 1, r, ql, qr);
}
void upd(int id, int l, int r, int pos, int val) {
if (l == r) {
st[id] += val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) upd(lid, l, mid, pos, val);
else upd(rid, mid + 1, r, pos, val);
st[id] = st[lid] + st[rid];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k, i, j, tmp, tmp2;
cin >> n >> m >> k;
adj.resize(n + 1);
for (i = 1; i <= n - 1; i++) {
cin >> tmp >> tmp2;
adj[tmp].push_back(make_pair(tmp2, i));
adj[tmp2].push_back(make_pair(tmp, i));
}
vector<vector<int>> ms(m);
for (i = 0; i < m; i++) {
cin >> tmp;
ms[i].resize(tmp);
for (j = 0; j < tmp; j++) cin >> ms[i][j];
}
tree.resize(n + 1);
buildTree(1);
for (int child : tree[1].childs) buildAnc(child);
st.resize(t * 4);
for (auto& mi : ms) {
mi.push_back(mi[0]);
for (i = 0; i < mi.size() - 1; i++) {
upd(0, 0, t - 1, tree[mi[i]].tin, 1);
upd(0, 0, t - 1, tree[mi[i]].tout, 1);
upd(0, 0, t - 1, tree[mi[i + 1]].tin, 1);
upd(0, 0, t - 1, tree[mi[i + 1]].tout, 1);
upd(0, 0, t - 1, tree[findLCA(mi[i], mi[i + 1])].tin, -2);
upd(0, 0, t - 1, tree[findLCA(mi[i], mi[i + 1])].tout, -2);
}
}
vector<int> ans;
for (i = 2; i <= n; i++) {
if (que(0, 0, t - 1, tree[i].tin, tree[i].tout) / 2 >= k * 2) ans.push_back(tree[i].parrid);
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for (int r : ans) cout << r << ' ';
return 0;
}
Compilation message (stderr)
railway.cpp: In function 'void buildAnc(int)':
railway.cpp:34:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | while (tree[id].anc.size() >= step + 1) {
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
railway.cpp: In function 'int findLCA(int, int)':
railway.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | while (pos >= tree[b].anc.size() or tree[tree[b].anc[pos]].depth < tree[a].depth) pos--;
| ~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (pos >= 0 and (pos >= tree[a].anc.size() or tree[a].anc[pos] == tree[b].anc[pos])) pos--;
| ~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (i = 0; i < mi.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~
# | 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... |