¡Buenos días, tardes o noches!
Acabo de resolver este problema y quiero saber si se puede mejorar la complejidad a NlogN o bien si alguien tiene ideas más lindas para la complejidad que me quedó a mí.
Mi solución corre en O(N logN) para la construcción y O(Q(log^2N)) para responder las queries.
Mi idea fue la siguiente
- Armar la estructura para obtener el LCA con una raíz arbitraria, la versión que usa Binary Lifting.
- Por cada query (r, u, v):
- Obtener el LCA c de (u, v).
- Hacer una Búsqueda Binaria en el camino (u, c) y (v, c) que encuentre el primer nodo x tal que la distancia del siguiente nodo del camino a r sea mayor que la distancia de x a r.
- Cada rama va a tener un candidato y me quedo con el que esté más cerca de r.
- Rogar que no de TLE. Pero bueno, dio AC gracias a los 3 segundos de tiempo.
Y el código
#include<bits/stdc++.h>
#define sp system("pause")
#define forn(i, n) for(int i = 0; i < n; i++)
using namespace std;
const int MAXN = 2E5 + 5, LOG = 19, RAIZ = 0;
struct lcaTable{
int level[MAXN], sparse[MAXN][LOG];
lcaTable(){
forn(i, MAXN) forn(j, LOG) sparse[i][j] = RAIZ;
level[RAIZ] = -1;
}
void insert(int u, int p){
level[u] = level[p] + 1;
sparse[u][0] = p;
for(int i = 1; i < LOG; i++) sparse[u][i] = sparse[sparse[u][i - 1]][i - 1];
}
int lca(int u, int v){
if(level[u] < level[v]) swap(u, v);
int i;
for(i = 0; level[u] - (1<<i) > level[v]; i++);
for(; level[u] > level[v]; i--){
if(level[u] - (1<<i) < level[v]) continue;
u = sparse[u][i];
}
if(u == v) return u;
for(i = 0; sparse[u][i] != sparse[v][i]; i++);
for(; i >= 0; i--){
if(sparse[u][i] == sparse[v][i]) continue;
u = sparse[u][i];
v = sparse[v][i];
}
return sparse[u][0];
}
int dist(int u, int v){
int c = lca(u, v);
return level[u] + level[v] - level[c] * 2;
}
int climb(int u, int k){
while(k){
int i = log2(k);
u = sparse[u][i];
k -= (1<<i);
}
return u;
}
int nearestNodeInPath(int u, int v, int r){ //Returns the nearest node to r in the path from u to v
//Is mandatory that 'v' is ancestor of 'u'
int d = level[u] - level[v];
int bl = -1, br = d, bh;
while(br - bl > 1){
bh = (bl + br) / 2;
int a = climb(u, bh), b = climb(u, bh + 1);
a = dist(a, r), b = dist(b, r);
if(a > b) bl = bh;
else br = bh;
}
int ret = climb(u, br);
return ret;
}
int query(int r, int u, int v){
int c = lca(u, v);
int a = nearestNodeInPath(u, c, r);
int b = nearestNodeInPath(v, c, r);
if(dist(a, r) < dist(b, r)) return a;
return b;
}
} lca;
vector<int> adj[MAXN];
void dfs(int u, int p){
lca.insert(u, p);
for(int v : adj[u]){
if(v == p) continue;
dfs(v, u);
}
}
int main(){
int n;
cin>>n;
forn(i, n - 1){
int u, v;
cin>>u>>v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0, 0);
int q;
cin>>q;
while(q--){
int r, u, v;
cin>>r>>u>>v;
r--, u--, v--;
cout<<(lca.query(r, u, v) + 1)<<"\n";
}
return 0;
}
Leo sus ideas, gracias :3
(pues entiendo que lo que más cuesta son los LCAs).