jzoj snow的追寻
DFS序上搞
合并暴力和，记录最长链和当前最远点，距离跑LCA
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
const int MAXN(1e5 + 10);
int n, ft[MAXN], cnt, Q;
int size[MAXN], fa[MAXN], top[MAXN], son[MAXN], dfn[MAXN], ed[MAXN], id[MAXN], dep[MAXN];
struct Edge{ int to, nt; } edge[MAXN << 1];
struct Data{ int u, v, len; } t[MAXN << 2], ans;
IL void Add(RG int u, RG int v){
edge[cnt] = (Edge){v, ft[u]}; ft[u] = cnt++;
}
IL void Dfs1(RG int u){
size[u] = 1;
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(size[v]) continue;
dep[v] = dep[u] + 1; fa[v] = u;
Dfs1(v);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
IL void Dfs2(RG int u, RG int Top){
top[u] = Top; dfn[u] = ++cnt; id[cnt] = u;
if(son[u]) Dfs2(son[u], Top);
for(RG int e = ft[u]; e != -1; e = edge[e].nt)
if(!dfn[edge[e].to]) Dfs2(edge[e].to, edge[e].to);
ed[u] = cnt;
}
IL ll Dis(RG int u, RG int v){
if(!u || !v) return 0;
RG ll dis = dep[u] + dep[v];
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
return dis - 2 * dep[u];
}
IL Data Merge(RG Data x, RG Data y){
RG int p[4] = {x.u, x.v, y.u, y.v};
x.len = x.u = x.v = 0;
for(RG int i = 0; i < 3; i++)
for(RG int j = i + 1; j < 4; j++){
RG ll dis = Dis(p[i], p[j]);
if(dis > x.len) x.len = dis, x.u = p[i], x.v = p[j];
}
return x;
}
IL void Query(RG int x, RG int l, RG int r, RG int L, RG int R){
if(l >= L && r <= R) ans = Merge(ans, t[x]);
else{
RG int mid = l + r >> 1;
if(mid >= L) Query(x << 1, l, mid, L, R);
if(mid < R) Query(x << 1 | 1, mid + 1, r, L, R);
}
}
IL void Build(RG int x, RG int l, RG int r){
if(l == r) t[x].u = t[x].v = id[l], t[x].len = 0;
else{
RG int mid = l + r >> 1, ls = x << 1, rs = x << 1 | 1;
Build(ls, l, mid); Build(rs, mid + 1, r);
t[x] = Merge(t[ls], t[rs]);
}
}
int main(RG int argc, RG char* argv[]){
Fill(ft, -1);
n = Read(); Q = Read();
for(RG int i = 1; i < n; i++){
RG int u = Read(), v = Read();
Add(u, v); Add(v, u);
}
cnt = 0; Dfs1(1); Dfs2(1, 1);
Build(1, 1, n);
while(Q--){
RG int u = Read(), v = Read();
if(u == 1 || v == 1){ puts("0"); continue; }
if(dfn[u] > dfn[v]) swap(u, v);
ans.u = ans.v = ans.len = 0;
if(dfn[u] > 1) Query(1, 1, n, 1, dfn[u] - 1);
if(ed[u] + 1 < dfn[v]) Query(1, 1, n, ed[u] + 1, dfn[v] - 1);
if(max(ed[v], ed[v]) < n) Query(1, 1, n, max(ed[v], ed[u]) + 1, n);
printf("%d
", ans.len);
}
return 0;
}