#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define tn int
#define pair pair< tn, tn >
#define fi first
#define se second
#define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ )
#define nguyenthao( i, a, b ) for( tn i = b; i >= a; i-- )
#define thaonguyenxinh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const tn N = 1e5 + 5;
const tn M = __lg(N) + 1;
pair railway[N];
map< pair, tn > mp;
vector<tn> g[N], vertex, result;
tn n, q, k, u, v, z, tmc, cnt[N], in[N], out[N], h[N], p[N][M], dp[N], valid[N], pp[N];
void bfs( tn u, tn par ){
in[u] = out[u] = ++tmc;
for( tn v : g[u] ){
if ( v == par )
continue;
pp[v] = u;
h[v] = h[u] + 1;
bfs( v, u );
dp[u] += dp[v];
p[v][0] = u;
out[u] = max( out[u], out[v] );
}
}
void initialize(){
thaonguyen( j, 1, __lg(n) )
thaonguyen( i, 1, n )
p[i][j] = p[p[i][j-1]][j-1];
}
tn lca( tn u, tn v ){
if ( h[u] < h[v] )
swap( u, v );
tn z = __lg( h[u] );
nguyenthao( i, 0, z )
if ( h[u] - h[v] >= ( 1 << i ) )
u = p[u][i];
if ( u == v )
return u;
nguyenthao( i, 0, z )
if ( p[u][i] != p[v][i] )
u = p[u][i],
v = p[v][i];
return p[u][0];
}
bool cmp( tn a, tn b ){
return in[a] < in[b];
}
void floyd( tn u, tn par ){
dp[u] = valid[u];
for( tn v : g[u] ){
if ( v == par )
continue;
floyd( v, u );
dp[u] += dp[v];
}
}
void dijkstra( tn u, tn par ){
dp[u] = 0; valid[u] = 0;
for( tn v : g[u] ){
if ( v == par or !dp[v] )
continue;
cnt[v]++;
dijkstra( v, u );
}
}
signed main(){
thaonguyenxinh;
freopen( "Railway.inp", "r", stdin );
freopen( "Railwat.out", "w", stdout );
cin >> n >> q >> k;
thaonguyen( i, 1, n - 1 ){
cin >> u >> v;
if ( u > v )
swap( u, v );
mp[ { u, v } ] = i;
g[u].push_back(v),
g[v].push_back(u);
}
bfs( 1, -1 ); initialize();
thaonguyen( j, 1, q ){
cin >> z; vertex.clear();
if ( z == 1 )
continue;
thaonguyen( i, 1, z ){
cin >> u; valid[u] = 1;
vertex.push_back(u);
}
sort( vertex.begin(), vertex.end(), cmp );
thaonguyen( i, 0, z - 2 )
vertex.push_back( lca( vertex[i], vertex[i+1] ) );
sort( vertex.begin(), vertex.end(), cmp );
floyd( vertex[0], pp[vertex[0]] );
dijkstra( vertex[0], pp[vertex[0]] );
}
thaonguyen( i, 1, n )
if ( cnt[i] >= k ){
tn a = i; tn b = pp[i];
if ( a > b )
swap( a, b );
result.push_back( mp[ { a, b } ] );
}
sort( result.begin(), result.end() );
cout << result.size() << endl;
for( tn v : result )
cout << v << " ";
}
Compilation message (stderr)
railway.cpp: In function 'int main()':
railway.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | freopen( "Railway.inp", "r", stdin );
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen( "Railwat.out", "w", stdout );
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |