#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
const int mxN = 1e5;
int n,k;
vector<pii> adj[mxN];
int bj[mxN][20];
int first[mxN];
int pidx[mxN];
int ssize[mxN];
int res[mxN];
int cnt = 0;
void dfs(int node, int p){
bj[node][0] = p;
for (int i = 1; i < 20; i++){
if (bj[node][i-1] == -1){
break;
}
bj[node][i] = bj[bj[node][i-1]][i-1];
}
first[node] = cnt;
cnt++;
ssize[node] = 1;
// cout << node << " -" << p << '\n';
for (pii next : adj[node]){
if (next.f != p){
dfs(next.f,node);
ssize[node] += ssize[next.f];
} else {
pidx[node] = next.s;
}
}
}
bool contain(int a, int b){
if (first[a] <= first[b] && ssize[a] + first[a] > first[b]){
return true;
}
return false;
}
int glca(int a, int b){
if (a == -1){
return b;
}
while (!contain(a,b)){
for (int i = 1; i < 20; i++){
if (bj[a][i] == -1 || contain(bj[a][i],b)){
a = bj[a][i-1];
break;
}
}
}
return a;
}
bool segtree[4*mxN+1];
void upd(int t, bool v, int l = 0, int r = n-1, int idx = 0){
if (l > t || r < t){
return;
}
if (l == r){
segtree[idx] = v;
return;
}
int m = (l+r)/2;
upd(t,v,l,m,2*idx+1);
upd(t,v,m+1,r,2*idx+2);
segtree[idx] = (segtree[2*idx+1] || segtree[2*idx+2]);
}
bool query(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
if (l > tr || r < tl){
return false;
}
if (l >= tl & r <= tr){
return segtree[idx];
}
int m = (l+r)/2;
return query(tl,tr,l,m,2*idx+1) || query(tl,tr,m+1,r,2*idx+2);
}
void addon(int a){
int next;
// cout << a << " : ";
while (!query(first[a],first[a]+ssize[a]-1)){
for (int i = 1; i < 20; i++){
next = bj[a][i];
if (next == -1 || query(first[next],first[next]+ssize[next]-1)){
a = bj[a][i-1];
break;
}
}
// cout << a << " ";
}
// cout << a << '\n';
res[a] -= 1;
}
vector<int> tot;
void solve(int node, int p){
for (pii next : adj[node]){
if (next.f != p){
solve(next.f,node);
res[node] += res[next.f];
}
}
if (res[node] >= k){
tot.pb(pidx[node]+1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
cin >> n >> m >> k;
int a,b;
for (int i =0; i < n-1; i++){
cin >> a >> b;
a -= 1;
b -= 1;
adj[a].pb({b,i});
adj[b].pb({a,i});
}
memset(res,0,sizeof(res));
memset(segtree,0,sizeof(segtree));
for (int i =0; i < mxN; i++) for (int j =0; j <20; j++) bj[i][j]=-1;
dfs(0,-1);
pidx[0] = -1;
int si,lca;
/* for (int i =0; i < n; i++) cout << first[i] << " ";
cout << '\n';
for (int i =0; i < n; i++) cout << ssize[i] << " ";
cout << '\n';*/
vector<int> all;
for (int i = 0; i < m; i++){
cin >> si;
lca = -1;
all.clear();
for (int j = 0; j < si; j++){
cin >> a;
a -= 1;
all.pb(a);
lca = glca(lca,a);
}
// cout << all[0] << '\n';
upd(first[all[0]],true);
res[all[0]]++;
res[lca]--;
for (int j = 1; j < all.size(); j++){
addon(all[j]);
res[all[j]]++;
upd(first[all[j]],true);
}
for (int j = 0; j < all.size(); j++){
upd(first[all[j]],false);
}
/* for (int j =0; j < n; j++){
cout << res[j] << " ";
}
cout << '\n';*/
}
solve(0,-1);
cout << (int) tot.size() << "\n";
for (int i : tot){
cout << i << " ";
}
cout << '\n';
return 0;
}
Compilation message
railway.cpp: In function 'bool query(int, int, int, int, int)':
railway.cpp:84:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
84 | if (l >= tl & r <= tr){
| ~~^~~~~
railway.cpp: In function 'int main()':
railway.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (int j = 1; j < all.size(); j++){
| ~~^~~~~~~~~~~~
railway.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int j = 0; j < all.size(); j++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
514 ms |
27596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
522 ms |
22640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
522 ms |
22640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
