题目
给定一棵树，每次询问：点 ([l,r]) 当中距离点 (x) 最近的距离是多少。
分析
点分树+线段树。
点分树的基础应用，首先我们可以把这里点分树上面的线段树拿来维护编号为 ([1,n]) 的所有结点的到当前点的距离最小值。
（当然有值的都是子树里面的，其他的是 (INF) ）
然后每次直接询问，跳父亲就好了。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=2e5+5,INF=1e9+7;
int n,k,m,val[N],Ans;
int head[N],to[N<<1],nex[N<<1],idx;
int st[N*3][21],pos[N],Euler,fa[N],lg[N*3],dis[N],dep[N];
bool vis[N];
vector<int> c[2][N];
inline void add(int u,int v,int w){
nex[++idx]=head[u];
to[idx]=v;
val[idx]=w;
head[u]=idx;
return ;
}
void EulerDfs(int x,int f){
fa[x]=f,dep[x]=dep[f]+1,st[++Euler][0]=x;pos[x]=Euler;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==f) continue;
dis[y]=dis[x]+val[i],EulerDfs(y,x);
st[++Euler][0]=x;
}
return ;
}
inline int GetMin(int x,int y){return dep[x]<dep[y]?x:y;}
void GetST(){
for(int i = 1; i <= Euler; ++i) lg[i] = 31 - __builtin_clz(i);
for(int j=1;(1<<j)<=Euler;j++) for(int i=1;i+(1<<j)<=Euler;i++) st[i][j]=GetMin(st[i][j-1],st[i+(1<<(j-1))][j-1]);
return ;
}
inline int QueryDis(int x,int y){
if(pos[x]>pos[y]) swap(x,y);
const int ql=pos[x],qr=pos[y],tmp=lg[qr-ql+1];
const int lca=GetMin(st[ql][tmp],st[qr-(1<<tmp)+1][tmp]);
return dis[x]+dis[y]-dis[lca]-dis[lca];
}
int FMax,Max,Root,Size,siz[N];
void GetRoot(int x,int f){
int Max=0;siz[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==f||vis[y]) continue;
GetRoot(y,x);siz[x]+=siz[y];
Max=max(Max,siz[y]);
}
Max=max(Max,Size-siz[x]);
if(Max<=FMax) FMax=Max,Root=x;
return ;
}
void Divide(int x){
vis[x]=true;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]) continue;
Size=siz[y],Root=y,FMax=INF,GetRoot(y,0),fa[Root]=x,Divide(Root);
}
return ;
}
int Rt1[N],Rt2[N],Min[N<<6],ls[N<<6],rs[N<<6],cur;
void Add(int &x,int l,int r,int pos,int v){
if(!x) x=++cur,Min[x]=INF;
if(l==r) return Min[x]=v,void();
int mid=l+r>>1;
if(pos<=mid) Add(ls[x],l,mid,pos,v);
else Add(rs[x],mid+1,r,pos,v);
Min[x]=min(Min[ls[x]],Min[rs[x]]);
return ;
}
int Ask(int x,int l,int r,int ql,int qr){
if(!x) return INF;
if(ql<=l&&r<=qr) return Min[x];
int mid=l+r>>1,res=INF;
if(ql<=mid) res=min(res,Ask(ls[x],l,mid,ql,qr));
if(qr>mid) res=min(res,Ask(rs[x],mid+1,r,ql,qr));
return res;
}
inline void Modify(int x){
for(int u=x;u;u=fa[u]) Add(Rt1[u],1,n,x,QueryDis(x,u));
return ;
}
inline int Query(int x,int l,int r){
Ans=Ask(Rt1[x],1,n,l,r);
for(int u=x;fa[u];u=fa[u]){
const int Dis=QueryDis(x,fa[u]);
Ans=min(Ans,Ask(Rt1[fa[u]],1,n,l,r)+Dis);
}
return Ans;
}
signed main(){
read(n);
for(int i=1;i<n;i++){
int u,v,w;
read(u),read(v),read(w);
add(u,v,w),add(v,u,w);
}
read(m);
EulerDfs(1,0);
GetST();
Size=n,Root=1,FMax=INF;Min[0]=INF;
GetRoot(1,0);fa[Root]=0;Divide(Root);
for(int i=1;i<=n;i++) Modify(i);
for(int i=1;i<=m;i++){
int x,l,r;read(l),read(r),read(x),write(Query(x,l,r)),putchar('
');
}
return 0;
}