楼房重建的思想，首先倍增预处理出来区间最小值，区间答案 \(f_{i,j}\) ( \(fa_{i,j}\) 跳到 \(i\) 的最小花费) ，那么考虑将上下两个区间合并，首先上区间直接算入答案就可以，设上区间最小值为 \(lim\)，那么考虑下区间，加入下区间最小值大于 \(lim\)，那么直接用上区间最小值跳下区间就可以；反之我们将下区间分成 \(A1\) 和 \(A2\) 两个区间，如果 \(A1\) 最小值大于 \(lim\) 那么递归考虑 \(A2\)；否则递归考虑 \(A1\)。
复杂度 \(O(n log^{2}n)\)
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3*1e5+10;
int n,m,t;
int head[N],nex[N*2],ver[N*2],edge[N*2],tot=0;
void add(int x,int y,int w){ver[++tot]=y,nex[tot]=head[x],head[x]=tot,edge[tot]=w;
}
struct T2{int dfn[N],num=0,fa[N],siz[N];void dfs(int x,int fat){fa[x]=fat;dfn[x]=++num;siz[x]=1;for(int i=head[x];i;i=nex[i]){int y=ver[i];if(y==fat) continue;dfs(y,x);siz[x]+=siz[y];}}int mp[3005][3005];int anss[3005][3004];int st[N],top,dist[N],rk[N];int f[N][50],g[N][50];void dfs1(int x,int fat){st[++top]=x;rk[x]=top;for(int i=head[x];i;i=nex[i]){int y=ver[i];if(y==fat) continue;dist[top+1]=dist[top]+edge[i];dfs1(y,x);}}int cnt[N],tp=0;void init(){dfs(1,0);dfs1(1,0);int op=top;for(int i=1;i<=n;i++){while(tp>0 && st[cnt[tp]]>st[i]){f[cnt[tp]][0]=i;tp--;}cnt[++tp]=i;}while(tp){f[cnt[tp]][0]=n;tp--;} for(int i=1;i<=n;i++) g[i][0]=(dist[f[i][0]]-dist[i])*st[i];int t=log2(n)+1;for(int j=1;j<=t;j++){for(int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];}}}void solve(){for(int p=1;p<=m;p++){int x,y;scanf("%lld%lld",&x,&y);if(dfn[y]>=dfn[x] && dfn[y]<=dfn[x]+siz[x]-1){int fx=rk[x],fy=rk[y];int ans=0;for(int i=t;i>=0;i--){if(f[fx][i]<=fy){ans+=g[fx][i];fx=f[fx][i];}}ans+=st[fx]*(dist[fy]-dist[fx]);printf("%lld\n",ans);}else printf("-1\n");}}
}T;
int dep[N],dist[N],fa[N][50],mn[N][50],f[N][50];
int dfn[N],num=0,siz[N];
int merge(int lim,int x,int k){if(mn[x][k]>=lim) return (dist[x]-dist[fa[x][k]])*lim;if(fa[x][k]<lim) return f[x][k];if(mn[fa[x][k-1]][k-1]>=lim) return lim*(dist[fa[x][k-1]]-dist[fa[x][k]])+merge(lim,x,k-1);else return f[x][k]-f[fa[x][k-1]][k-1]+merge(lim,fa[x][k-1],k-1);
}
void dfs(int x,int fat){dfn[x]=++num;siz[x]=1;dep[x]=dep[fat]+1;fa[x][0]=mn[x][0]=fat;for(int j=1;j<=t;j++){int i=x;fa[i][j]=fa[fa[i][j-1]][j-1];mn[i][j]=min(mn[i][j-1],mn[fa[i][j-1]][j-1]);f[i][j]=f[fa[i][j-1]][j-1]+merge(mn[fa[i][j-1]][j-1],i,j-1);}for(int i=head[x];i;i=nex[i]){int y=ver[i];if(y==fat) continue;dist[y]=dist[x]+edge[i];f[y][0]=edge[i]*x;dfs(y,x);siz[x]+=siz[y];}
}
struct asd{int x,k;
}st[N];
int solve(int x,int y){int top=0;int tmp=y;for(int j=t;j>=0;j--){if(dep[fa[tmp][j]]>=dep[x]){st[++top]={tmp,j};tmp=fa[tmp][j];}}int ans=f[st[top].x][st[top].k];int lim=mn[st[top].x][st[top].k];for(int i=top-1;i>=1;i--){ans+=merge(lim,st[i].x,st[i].k);lim=min(lim,mn[st[i].x][st[i].k]);}return ans;
}
int du[N];
signed main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%lld%lld",&n,&m);t=log2(n)+1;for(int i=1;i<n;i++){int x,y,w;scanf("%lld%lld%lld",&x,&y,&w);add(x,y,w),add(y,x,w);du[x]++,du[y]++;}int op=0;for(int i=1;i<=n;i++){if(du[i]>2) op=1;}if(!op){T.init();T.solve();return 0;}dfs(1,0);for(int i=1;i<=m;i++){int x,y;scanf("%lld%lld",&x,&y);if(dfn[y]>=dfn[x] && dfn[y]<=dfn[x]+siz[x]-1){printf("%lld\n",solve(x,y));}else printf("-1\n");}
}