Untitled
unknown
plain_text
a year ago
4.4 kB
16
Indexable
#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;
}Editor is loading...
Leave a Comment