Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //This Time Fire Is Different
- #include<bits/stdc++.h>
- using namespace std;
- #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
- #define ll long long
- #define ld long double
- #define pb push_back
- #define fe first
- #define se second
- #define nl "\n"
- #define pp pair < ll , ll >
- #define sz(x) (ll)x.size()
- #define st(x) sort(x.begin(),x.end())
- #define rst(x) sort(x.rbegin(), x.rend())
- #define all(x) x.begin(),x.end()
- long double pi = 3.14159265358979323;
- const double EPS = 1e-12;
- const int N = 1e3 + 5;
- const int mod = 1e9 + 7;
- ll n;
- vector < ll > v[N];
- ll l ;
- ll up[N][11];
- ll tin[N] ,tout[N];
- ll timer;
- void dfs(ll s , ll p){
- up[s][0] = p;
- tin[s] = timer++;
- for(int i = 1 ; i <= l ; i++ ){
- up[s][i] = up[up[s][i-1]][i-1];
- }
- //vis[s] = 1;
- for(auto it :v[s]){
- if(it != p){
- dfs(it,s);
- }
- }
- tout[s] = timer++;
- }
- bool is_ances(ll u , ll v){
- return (tin[u] <= tin[v] && tout[u] >= tout[v]);
- }
- ll lca(ll u , ll v){
- if(is_ances(u,v)){
- return u;
- }
- if(is_ances(v,u)){
- return v;
- }
- for(int i = l ; i >= 0 ; i--){
- if(!is_ances(up[u][i],v)){
- u = up[u][i];
- }
- }
- return up[u][0];
- }
- int main()
- {
- fast;
- ll t;
- cin >> t ;
- for(int i = 1 ; i <= t ; i++ ){
- ll n;
- cin >> n ;
- l = log2(n);
- for(int i = 1 ; i <= n ; i++ ){
- ll m;
- cin >> m;
- while(m--){
- ll x;
- cin >> x ;
- v[i].pb(x);
- v[x].pb(i);
- }
- }
- dfs(1,1);
- ll q;
- cin >> q ;
- cout << "Case " << i << ":\n";
- while(q--){
- ll x , y;
- cin >> x >> y ;
- cout << lca(x,y) << "\n";
- }
- for(int i = 1 ; i <= n ; i++ ){
- v[i].clear();
- //vis[i] = 0 ;
- //level[i] = 0 ;
- for(int j = 0 ; j < 11 ; j++ )
- up[i][j] = 0 ;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement