Untitled
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