李超线段树二次离线。
容易发现，将和某个点 \(x\) 相邻的边权翻若干倍后，直径所在位置有两种可能：经过或不经过该点。不经过可以跑一次直接求，否则还要分类讨论一下。
- \(\operatorname{deg}_x=1\)
那么它会作为直径的一个端点。
- 否则
直径会从一条边进，另一条边出。
前者是简单的，后者发现将 \(x\) 变为根后，直径长度可以写成 \(\max_{(x,u,w)\in E}(w\times k+dis_u)+\operatorname{secmax}_{(x,u,w)\in E}(w\times k+dis_u)\)，其中 \(dis_i\) 表示点 \(i\) 到以 \(i\) 为根的子树中的点距离的最大值。
这是若干个一次函数的形式，可以上李超树维护。但是要求次大值，怎么办呢？可以考虑先求出最大值的位置，并求出除了这个位置外的最大值。发现这是一段前缀加一段后缀。把这个问题再离线下来跑一次就行了。
code：
点击查看代码
bool Mbe;
int n,m,q,V=1e9,c[N],fa[N];
ll firlen,ans[N],res[N],dw[N],up[N];
int tot,head[N];
vector<pii> g[N],h[N][2];
struct node{int to,nxt,cw;}e[N<<1];
struct Node{ll k,b;}ln[N];
il void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
il ll calc(int i,ll x){return ln[i].k*x+ln[i].b;}
struct SGT{
int tr[M],ls[M],rs[M],cur,rt;
il void init(){while(cur)tr[cur]=ls[cur]=rs[cur]=0,cur--;rt=0;}
void update(int l,int r,int &o,int x){
if(!o)o=++cur;
if(l==r){
if(calc(x,l)>calc(tr[o],l))tr[o]=x;
return;
}
int mid=(l+r)>>1;
if(calc(x,mid)>calc(tr[o],mid))swap(x,tr[o]);
if(calc(x,l)>calc(tr[o],l))update(l,mid,ls[o],x);
else update(mid+1,r,rs[o],x);
}
int query(int l,int r,int o,int x){
if(!o||l==r)return tr[o];
int mid=(l+r)>>1,ret=0;
if(x<=mid)ret=query(l,mid,ls[o],x);
else ret=query(mid+1,r,rs[o],x);
if(!ret||!tr[o])return ret|tr[o];
return calc(ret,x)>calc(tr[o],x)?ret:tr[o];
}
}T;
void dfs1(int u,int f){
go(i,u){
int v=e[i].to;
if(v==f)continue;
dfs1(v,u),dw[u]=max(dw[u],dw[v]+e[i].cw);
}
}
void dfs2(int u,int f){
ll mx=0,secmx=0;fa[u]=f;
go(i,u){
int v=e[i].to;
if(v==f)continue;
if(dw[v]+e[i].cw>mx)secmx=mx,mx=dw[v]+e[i].cw;
else if(dw[v]+e[i].cw>secmx)secmx=dw[v]+e[i].cw;
}
go(i,u){
int v=e[i].to;
if(v==f)continue;
if(dw[v]+e[i].cw==mx)up[v]=max(up[u]+c[u],secmx);
else up[v]=max(up[u]+c[u],mx);
c[v]=e[i].cw,dfs2(v,u);
}
if(up[u]>mx)secmx=mx,mx=up[u];
else if(up[u]>secmx)secmx=up[u];
firlen=max(firlen,mx+secmx);
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n-1){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
dfs1(1,0),dfs2(1,0);
scanf("%d",&q);
rep(i,1,q){
int x,y;scanf("%d%d",&x,&y);
g[x].eb(Mp(y,i));
}
rep(u,1,n){
T.init(),m=0;
go(i,u){
int v=e[i].to;
if(v==fa[u])continue;
ln[++m]={e[i].cw,dw[v]};
}
if(u!=1)ln[++m]={c[u],up[u]};
rep(i,1,m)T.update(1,V,T.rt,i);
if(m==1){
for(auto [i,j]:g[u])ans[j]=calc(T.query(1,V,T.rt,i),i);
continue;
}
rep(i,1,m)h[i][0].clear(),h[i][1].clear();
for(auto [i,j]:g[u]){
int p=T.query(1,V,T.rt,i);
ans[j]=calc(p,i);
h[p-1][0].eb(Mp(i,j));
h[p+1][1].eb(Mp(i,j));
}
T.init();
rep(i,1,m){
T.update(1,V,T.rt,i);
for(auto [j,k]:h[i][0])res[k]=max(res[k],calc(T.query(1,V,T.rt,j),j));
}
T.init();
drep(i,m,1){
T.update(1,V,T.rt,i);
for(auto [j,k]:h[i][1])res[k]=max(res[k],calc(T.query(1,V,T.rt,j),j));
}
}
rep(i,1,q)printf("%lld\n",max(firlen,ans[i]+res[i]));
}
bool Med;
signed main(){
cerr<<1.*(&Mbe-&Med)/1048576<<'\n';
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}