题意,给一棵树,每次给两个点(x,y),求(max_{i=1}^{n}(min(di_{x,i},di_{y,i})))
看std看了好久
以下是一个优秀的在线做法,(O(nlogn))预处理,每次询问可以做到(O(1))
首先把直径扣出来,然后就可以把整棵树看成一条直径上挂了n棵树,预处理每个点到直径的最短距离,和直径上每个点挂的树中距离这个点最远的距离(d_i)
对于每次询问,造成答案的点要么是直径的端点,要么是两个点路径上的某个直径点挂的树的最远距离的点,于是可以分类讨论.第一类比较好算,第二类的话,用个st表存(d_i),每次在距离(x)和(y)更近的区间内取最大值,再加加减减
详见代码
#include<bits/stdc++.h>
#define il inline
#define re register
#define LL long long
#define ull unsigned long long
#define db double
#define eps (1e-7)
using namespace std;
const int N=100000+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
int n,nn,m,st[N],de[N],fa[N],a1,a2,rtt,id[N],d[N],lz[N];
int ma[N][18],mi[N][18];
bool v[N];
void dfs(int x,int ffa)
{
if(de[x]>de[rtt]) rtt=x;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==ffa) continue;
de[y]=de[x]+1,fa[y]=x;
dfs(y,x);
}
}
void dd(int x,int ffa,int ii)
{
id[x]=ii,de[x]=de[ffa]+1; //把深度处理成到直径上点的距离
d[ii]=max(d[ii],de[x]);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==ffa||v[y]) continue;
dd(y,x,ii);
}
}
il void init()
{
for(int i=1;i<=m;i++) dd(st[i],0,i),lz[i]=log2(i);
for(int i=1;i<=m;i++) ma[i][0]=d[i]+i,mi[i][0]=d[i]-i;
for(int j=1;j<=nn;j++)
for(int i=1;i+(1<<(j-1))<=m;i++)
{
ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
mi[i][j]=max(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
}
il int quer(int l,int r,int o)
{
if(l>r) return -1e9;
int j=lz[r-l+1];
if(o==1) return max(mi[l][j],mi[r-(1<<j)+1][j]);
return max(ma[l][j],ma[r-(1<<j)+1][j]);
}
int main()
{
n=rd();
nn=log(n)/log(2)+1;
for(int i=1;i<n;i++)
{
int x=rd(),y=rd();
add(x,y);
}
dfs(1,0),a1=rtt,rtt=0,fa[a1]=0,dfs(a1,0),a2=rtt;
int nw=a2;
while(nw)
{
st[++m]=nw,v[nw]=true,nw=fa[nw];
}
for(int i=1;i<=m/2;i++) swap(st[i],st[m-i+1]);
de[0]=-1,init();
int q=rd(),an=0;
while(q--)
{
int x=rd(),y=rd();
an=0;
if(id[x]>id[y]) swap(x,y);
LL ss=id[x]-de[x]+id[y]+de[y]; //ss其实是x和y路径上中间点的直径点编号*2
if(id[x]==id[y]) an=max(id[x]-1,m-id[y])+min(de[x],de[y]);
else if(ss<=id[x]*2) an=max(id[y]-1,m-id[y])+de[y];
else if(ss>=id[y]*2) an=max(id[x]-1,m-id[x])+de[x];
else ss/=2,an=max(max(id[x]-1,quer(id[x]+1,ss,0)-id[x])+de[x],de[y]+max(m-id[y],quer(ss+1,id[y]-1,1)+id[y])); //对于x,到中间点区间内的答案为max(id[i]-id[x]+d[i]),y类似
printf("%d
",an);
}
return 0;
}