看到统计统计路径按照套路我们应该想到点分治。
在点分树上每个节点i建一棵线段树，支持查询区间最小值，倘若编号为j的点在点分树上是i的子树里的节点，那么i的这棵线段树下标j存的就是i到j在原树上的距离。
询问的时候考虑把路径拼接就行了。
时间复杂度 (O(nlog^2n))
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,l,r,tot,x,y,z,now,ans;
const int N=100010;
int head[N],to[N<<1],nt[N<<1],len[N<<1];
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
void add(int f,int t,int d)
{
to[++tot]=t;len[tot]=d;nt[tot]=head[f];head[f]=tot;
}
namespace shu
{
int cnt;
int fa[N],dep[N],DEP[N],son[N],siz[N],top[N],dfn[N];
void dfs1(int x,int f)
{
dep[x]=dep[f]+1;siz[x]=1;fa[x]=f;
for(int i=head[x];i;i=nt[i])
if(to[i]!=f)
{
DEP[to[i]]=DEP[x]+len[i];
dfs1(to[i],x);siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]])son[x]=to[i];
}
}
void dfs2(int x,int t)
{
dfn[x]=++cnt;top[x]=t;
if(son[x])dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])dfs2(to[i],to[i]);
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int DIS(int x,int y)
{
return DEP[x]+DEP[y]-2*DEP[LCA(x,y)];
}
}
namespace dfz
{
int root,num;
int fa[N],siz[N],mx[N],vis[N];
void YYCH()
{
num=n;root=0;mx[0]=1<<30;
}
void Groot(int x,int fa)
{
siz[x]=1;mx[x]=0;
for(int i=head[x];i;i=nt[i])
if(!vis[to[i]]&&to[i]!=fa)
{
Groot(to[i],x);
siz[x]+=siz[to[i]];mx[x]=max(mx[x],siz[to[i]]);
}
mx[x]=max(mx[x],num-siz[x]);
if(mx[x]<mx[root])root=x;
}
void solve(int x)
{
vis[x]=1;
for(int i=head[x];i;i=nt[i])
if(!vis[to[i]])
{
num=siz[to[i]];root=0;
Groot(to[i],0);fa[root]=x;
solve(root);
}
}
}
namespace xds
{
int cnt;
int root[N],lson[N*17*17],rson[N*17*17],tr[N*17*17];
void YYCH()
{
tr[0]=2e9;
}
void pushup(int k){tr[k]=min(tr[lson[k]],tr[rson[k]]);}
void Insert(int &k,int l,int r,int pos,int val)
{
if(!k)k=++cnt;
if(l==r)
{
tr[k]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)Insert(lson[k],l,mid,pos,val);
else Insert(rson[k],mid+1,r,pos,val);
pushup(k);
}
int ask(int k,int l,int r,int x,int y)
{
if((x<=l&&r<=y)||(!k))return tr[k];
int mid=(l+r)>>1,res=2e9;
if(x<=mid)res=min(res,ask(lson[k],l,mid,x,y));
if(mid+1<=y)res=min(res,ask(rson[k],mid+1,r,x,y));
return res;
}
}
void solve2()//kao,不用莫队。。。
{
shu::dfs1(1,0);shu::dfs2(1,1);
dfz::YYCH();dfz::Groot(1,0);dfz::solve(dfz::root);
xds::YYCH();
for(int i=1;i<=n;++i)
{
now=i;
while(now)
{
xds::Insert(xds::root[now],1,n,i,shu::DIS(i,now));
now=dfz::fa[now];
}
}
while(m--)
{
ans=2e9;
l=read();r=read();now=x=read();
while(now)
{
ans=min(ans,xds::ask(xds::root[now],1,n,l,r)+shu::DIS(now,x));
now=dfz::fa[now];
}
printf("%d
",ans);
}
}
int main()
{
cin>>n;
for(int i=1;i<n;++i)
x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
cin>>m;
solve2();
return 0;
}