Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
4.4 kB
0
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()), ((v).end())
#define yes cout << "YES" << '\n';
#define no cout << "NO" << '\n';
#define endl '\n'
typedef long long ll;
const int N=5e5+1;
struct lca_lift {
  const int lg = 24;
  int n;
  vector<int> depth;
  vector<vector<int> > edges;
  vector<vector<int> > lift;

  void init(int sz) {
    n = sz;
    depth = vector<int>(n);
    edges = vector<vector<int> >(n, vector<int>());
    lift = vector<vector<int> >(n, vector<int>(lg, -1));
  }

  void edge(int a, int b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  void attach(int node_to_attach, int node_to_attach_to) {
    int a = node_to_attach, b = node_to_attach_to;
    edge(a, b);

    lift[a][0] = b;

    for (int i = 1; i < lg; i++) {
      if (lift[a][i - 1] == -1) lift[a][i] = -1;
      else lift[a][i] = lift[lift[a][i - 1]][i - 1];
    }

    depth[a] = depth[b] + 1;
  }

  void init_lift(int v = 0) {
    depth[v] = 0;
    dfs(v, -1);
  }

  void dfs(int v, int par) {
    lift[v][0] = par;

    for (int i = 1; i < lg; i++) {
      if (lift[v][i - 1] == -1) lift[v][i] = -1;
      else lift[v][i] = lift[lift[v][i - 1]][i - 1];
    }

    for (int x: edges[v]) {
      if (x != par) {
        depth[x] = depth[v] + 1;
        dfs(x, v);
      }
    }
  }

  int get(int v, int k) {
    for (int i = lg - 1; i >= 0; i--) {
	  if (v == -1) return v;
      if ((1 << i) <= k) {
        v = lift[v][i];
        k -= (1 << i);
      }
    }
    return v;
  }

  int get_lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    int d = depth[a] - depth[b];
    int v = get(a, d);
    if (v == b) {
      return v;
    } else {
      for (int i = lg - 1; i >= 0; i--) {
        if (lift[v][i] != lift[b][i]) {
          v = lift[v][i];
          b = lift[b][i];
        }
      }
      return lift[b][0];
    }
  }

  int get_dist(int a, int b) {
	  int v = get_lca(a, b);
	  return depth[a] + depth[b] - 2 * depth[v];
  }
};
vector<ll> sz(N,1);
vector<ll> adj[N];
int dfs(int i,int par)
{
    for (auto x:adj[i])
    {
        if (x==par)
            continue;
            dfs(x,i);
            sz[i]+=sz[x];


    }
  //  cout << i << ' ' << sz[i] << endl;
    return sz[i];
}
void solve() {
    int n;
    cin >> n;
    lca_lift lca;
    lca.init(n);
   for (int i=0;i<n-1;i++)
   {
       int x,y;
       cin >> x >> y;
       --x;
       --y;
       adj[x].push_back(y);
       adj[y].push_back(x);
      // --x;
      // --y;
       lca.edge(x,y);
   }
   ll start=-1;
    lca.init_lift();
   ll q;
   cin >> q;
   vector<pair<int,int>> vp(q);
   for (int i=0;i<q;i++)
   {
       cin >> vp[i].first>> vp[i].second;
       --vp[i].first;
       --vp[i].second;

   }
    start =0;
   dfs(start,-1);
   for (int i=0;i<q;i++)
   {
       int x=vp[i].first;
       int y=vp[i].second;
       int d=lca.get_dist(x,y);
       int p=lca.get_lca(x,y);
       int d1=lca.depth[x];
       int d2=lca.depth[y];
      // cout << x << ' ' << y  << endl;
       int a=0;
       int b=0;
       if (d1<d2)
       {
           if (d%2==0)
           {
               int pp=lca.get(y,d/2);
               int ny=lca.get(y,d/2-1);
               a=n-sz[pp];
               b=sz[ny];

           }else
           {
               int pp=lca.get(y,d/2);
               //cout << pp << endl;

               a=n-sz[pp];
               b=sz[pp];
           }
       }else if (d2<d1)
       {
           if (d%2==0)
           {
               int pp=lca.get(x,d/2);
               int ny=lca.get(x,d/2-1);
               b=n-sz[pp];
               a=sz[ny];

           }else
           {
               int pp=lca.get(x,d/2);

               b=n-sz[pp];
               a=sz[pp];
           }
       }else if (d1==d2)
       {
            int nx=lca.get(x,lca.get_dist(x,p)-1);
            int ny=lca.get(y,lca.get_dist(y,p)-1);
            a=sz[nx];
            b=sz[ny];
       }
      // cout << a << ' ' << b << endl;
       if (a>b)
       {
           cout << "Alice\n";
       }else if (b>a)
       {
           cout << "Bob\n";
       }else
       {
           cout << "Draw\n";
       }
   }











}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int testcases = 1;
   // cin >> testcases;
    while (testcases--) {


        solve();
    }
    return 0;
}
Leave a Comment