#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
vector<vector<pair<int,int> > > adj(maxn);
vector<int> cnt(maxn,0);
vector<int> vect1;
vector<int> seg(maxn*12,0);
vector<int> depth(maxn,INT_MAX);
vector<int> pos(maxn);
int no_of_vertex,no_of_people,mini;
void build(int node,int start,int end){
if(start==end){
seg[node] = vect1[start];
return;
}
int mid = (start+end)/2;
build(node*2+1,start,mid);
build(node*2+2,mid+1,end);
if(depth[seg[node*2*2]]>depth[seg[node*2+1]]){
seg[node] = seg[node*2+1];
}
else{
seg[node] = seg[node*2+2];
}
}
int query(int node,int start,int end,int rangemin,int rangemax){
if(start>=rangemin&&end<=rangemax){
return seg[node];
}
if(start>rangemax||end<rangemin){
return -1;
}
int mid = (start+end)/2;
int left = query(node*2+1,start,mid,rangemin,rangemax);
int right = query(node*2+2,mid+1,end,rangemin,rangemax);
if(left==-1){
return right;
}
if(right==-1){
return left;
}
if(depth[right]>depth[left]){
return left;
}
else{
return right;
}
}
void dfs(int node,int parent,int d){
pos[node] = (int)vect1.size()-1;
vect1.push_back(node);
depth[node] = d;
for(auto k:adj[node]){
if(k.first!=parent){
dfs(k.first,node,d+1);
vect1.push_back(node);
}
}
}
vector<int> ans;
void dfs2(int node,int parent,int last){
for(auto k:adj[node]){
if(k.first!=parent){
dfs2(k.first,node,k.second);
cnt[node] += cnt[k.first];
}
}
if(cnt[node]>=mini){
ans.push_back(last);
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int no_of_input;
int input1,input2,input3,input;
cin >> no_of_vertex >> no_of_people >> mini;
for(int i=0;i<no_of_vertex-1;i++){
cin >> input1 >> input2;
adj[input1].push_back({input2,i});
adj[input2].push_back({input1,i});
}
dfs(1,-1,0);
build(0,0,vect1.size()-1);
for(int i=0;i<no_of_people;i++){
cin >> no_of_input >> input1 >> input2;
assert(no_of_input==2);
int lca = query(0,0,vect1.size()-1,min(pos[input1],pos[input2]),max(pos[input1],pos[input2]));
cnt[input1]++;
cnt[input2]++;
cnt[lca] -= 2;
}
/*for(int i=1;i<=no_of_vertex;i++){
for(int j=1;j<=no_of_vertex;j++){
cout << i << " " << j << " " << query(0,0,vect1.size()-1,min(pos[i],pos[j]),max(pos[i],pos[j])) << "\n";
}
}*/
dfs2(1,-1,-1);
sort(ans.begin(),ans.end());
cout << ans.size() << '\n';
for(auto k:ans){
cout << k+1 << " ";
}
}
Compilation message
railway.cpp: In function 'int32_t main()':
railway.cpp:76:23: warning: unused variable 'input3' [-Wunused-variable]
int input1,input2,input3,input;
^~~~~~
railway.cpp:76:30: warning: unused variable 'input' [-Wunused-variable]
int input1,input2,input3,input;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 2 |
Runtime error |
24 ms |
18432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 2 |
Runtime error |
24 ms |
18432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
21612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
17056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
17056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 2 |
Runtime error |
24 ms |
18432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
