이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , m , k;
vector < pair < pii , int > > e;
vector < int > adj[maxn];
vector < int > ans;
int head[maxn] , par[maxn] , h[maxn] , sz[maxn] , mx[maxn] , st[maxn] , ft[maxn] , ti = 0;
void szdfs(int v){
sz[v] = 1;
for(auto u : adj[v])if(u ^ par[v]){
par[u] = v , h[u] = h[v] + 1 , szdfs(u) , sz[v] += sz[u];
if(sz[u] > sz[mx[v]])mx[v] = u;
}
}
void hldfs(int v){
st[v] = ++ti;
if(mx[v])head[mx[v]] = head[v] , hldfs(mx[v]);
for(auto u : adj[v])if(u^par[v] and u^mx[v])
head[u] = u , hldfs(u);
ft[v] = ti;
}
int lca(int u , int v){
while(head[u] ^ head[v]){
if(h[head[u]] < h[head[v]])swap(u , v);
u = par[head[u]];
}
return((h[u] < h[v]) ? u : v);
}
int fen[maxn];
void add(int pos , int x){
for(; pos < maxn ; pos += pos & -pos)
fen[pos] += x;
}
void add(int l , int r , int x){
add(l , x);
add(r + 1 , -x);
}
int get(int pos){
int res = 0;
for(; pos ; pos -= pos & -pos)
res += fen[pos];
return(res);
}
void addpath(int v , int anc){
while(head[v] ^ head[anc]){
add(st[head[v]] , st[v] , 1);
v = par[head[v]];
}
add(st[anc] , st[v] , 1);
add(st[anc] , st[anc] , -1);
}
void Add(int u , int v){
int lc = lca(u , v);
addpath(u , lc);
addpath(v , lc);
}
int32_t main(){
migmig;
cin >> n >> m >> k;
for(int i = 1 ; i < n ; i ++){
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
e.pb({{u , v} , i});
}
h[1] = 1;
szdfs(1);
hldfs(1);
while(m --){
int k;
cin >> k;
vector < int > vec(k);
for(int i = 0 ; i < k ; i ++)
cin >> vec[i];
sort(vec.begin() , vec.end() , [](int i , int j){return st[i] < st[j];});
vec.pb(vec[0]);
for(int i = 0 ; i < k ; i ++)
Add(vec[i] , vec[i + 1]);
}
for(auto x : e){
int v = x.first.first;
int u = x.first.second;
int i = x.second;
if(par[u] ^ v)swap(u , v);
if(get(st[u]) >= 2 * k)ans.pb(i);
}
cout << ans.size() << endl;
for(auto e : ans)
cout << e << ' ';
return(0);
}
# | 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... |