现有一棵大小为$105$的有边权树和最多$105$次询问，每次询问树上两点$u$到$v$需要的最短时间
与直接求路径长度不同的是，你的速度是可以变化的。你的初始速度$c=1$，在可以练习的地点，你可以花费时间$T$使得你的速度$c = c \times 2$，而你经过每条路径所需的时间为$ \lceil \frac{w_i}{c} \rceil $。
易得以下三点
- 对于一组询问，你的移动路径有可能会经过重复的点
- 你一定只在第一个经过的可以练习的点进行练习
- 练习次数不会超过$\max_{i=1}^n w_i$，答案不会超过$2 \times 10^9$
对于当前速度为$c=2^k$，在任意两点$u$，$v$之间移动所需时间，把这个值设为$dis_{u,v,k}$
我们首先可以倍增预处理一个点到他所有$2$的整数次方的父亲，然后在$log_2n$的时间内求出$dis_{u,v,k}$
如果我们的路径不是从$u$直达$v$，那么一定是从某个点离开路径练车，再由这个点返回路径
出发点为$u$，终点为$v$，假设我们从点$x$离开路径，在点$y$练车，我们所需要的时间就是
$$
\min_{i=1}^{20} dis_{u,x,0} + dis_{x,y,0} + dis_{y,x,i} + dis_{x,v,i} + T \times i \qquad OR \qquad dis_{u,v,0}
$$
后者我们可以直接求出，前者我们先用$BFS$维护出每个点$x$前往一个点练车$i$次然后回到该点的最小时间，把这个值设为$diss_{x,i}$
可以对倍增中的每个区间$x$到他的往上第$2^y$个父亲，维护出
$$
dis1_{x,y,i} = 从x出发，练了0次车，最后到达y父亲，练了i次车的最小时间\
dis2_{x,y,i} = 从x的y父亲出发，练了0次车，最后到达x，练了i次车的最小时间\
dis1_{x,0,i} = dis2_{x,0,i} = diss_{x,i}\
dis1_{x,y,i} = min(dis1_{x,y-1,i}+dis_{f_{x,y-1},y-1,i},dis_{x,y-1,0}+dis1_{f_{x,y-1},y-1,i})\
dis2_{x,y,i} = min(dis2_{x,y-1,i}+dis_{f_{x,y-1},y-1,0},dis_{x,y-1,i}+dis1_{f_{x,y-1},y-1,i})\
$$
然后对每个区间都按照这个求一遍最小的距离，一定包含最优解
开$long \ long$会mle，每个区间的答案对$2 \times 20^9$取$min$
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define bi (1<<i)
using namespace std;
int dis[100005][18][21],diss[100005][21];
int dis1[100005][18][21],dis2[100005][18][21];
int fa[100005][18],dep[100005];
bool vis[100005],vs[100005];
vector<pii>e[100005];
int n;
ll t;
int add(int x,int y){
return min((ll)2e9,(ll)x+y);
}
void dfs(int x,int f){
vis[x]=1;
fa[x][0]=f;
dep[x]=dep[f]+1;
for(int i=1;i<=20;i++){
dis[x][0][i]=dis[x][0][0]>>i;
if(dis[x][0][0]%bi)dis[x][0][i]++;
}
for(int i=1;i<=17;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int j=0;j<=20;j++)
dis[x][i][j]=add(dis[fa[x][i-1]][i-1][j],dis[x][i-1][j]);
}
for(int i=0;i<=20;i++){
dis1[x][0][i]=add(diss[x][i],dis[x][0][i]);
dis2[x][0][i]=add(diss[f][i],dis[x][0][i]);
}
for(int i=1;i<=17;i++)
for(int j=0;j<=20;j++){
int f=fa[x][i-1];
dis1[x][i][j]=min(add(dis1[x][i-1][j],dis[f][i-1][j]),add(dis[x][i-1][0],dis1[f][i-1][j]));
dis2[x][i][j]=min(add(dis2[x][i-1][j],dis[f][i-1][0]),add(dis[x][i-1][j],dis2[f][i-1][j]));
}
for(auto u:e[x])
if(!vis[u.first]){
dis[u.first][0][0]=u.second;
dfs(u.first,x);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=17;i>=0;i--)
if(dep[u]-dep[v]>=bi)u=fa[u][i];
if(u==v)return u;
for(int i=17;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
ll sum(int u,int v,int m){
ll cnt=0;
int l=lca(u,v);
for(int i=17;i>=0;i--){
if(dep[u]-dep[l]>=bi)
cnt+=dis[u][i][m],u=fa[u][i];
if(dep[v]-dep[l]>=bi)
cnt+=dis[v][i][m],v=fa[v][i];
}
return cnt;
}
ll qry(int u,int v){
int l=lca(u,v);
ll cnt[21],ans=sum(u,v,0);
for(int i=0;i<=20;i++)cnt[i]=0;
for(int i=17;i>=0;i--)
if(dep[u]-dep[l]>=bi){
int f=fa[u][i];
for(int j=1;j<=20;j++)
ans=min(ans,dis1[u][i][j]+sum(f,v,j)+cnt[0]+t*j);
cnt[0]+=dis[u][i][0];
u=fa[u][i];
}
for(int i=17;i>=0;i--)
if(dep[v]-dep[l]>=bi){
int f=fa[v][i];
for(int j=1;j<=20;j++){
ans=min(ans,dis2[v][i][j]+sum(f,u,0)+cnt[0]+cnt[j]+t*j);
cnt[j]+=dis[v][i][j];
}
v=fa[v][i];
}
return ans;
}
void bfs(int x){
priority_queue<pli,vector<pli>,greater<pli>>q;
for(int i=1;i<=n;i++){
diss[i][x]=1e18;
if(vs[i]){
q.push({0,i});
diss[i][x]=0;
}
}
while(!q.empty()){
int now=q.top().second;
ll d=q.top().first;
q.pop();
if(d>diss[now][x])continue;
for(auto u:e[now])
if(diss[u.first][x]>d+1+(u.second-1>>x)+u.second){
diss[u.first][x]=d+1+(u.second-1>>x)+u.second;
if(diss[u.first][x]>=2e9)continue;
q.push({diss[u.first][x],u.first});
}
}
}
void solve(){
scanf("%d%lld",&n,&t);
for(int i=1;i<=n;i++){
vis[i]=0;
e[i].clear();
}
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].push_back({v,w});
e[v].push_back({u,w});
}
for(int i=1;i<=n;i++){
int x;
scanf("%1d",&x);
vs[i]=x;
}
for(int i=0;i<=20;i++)
bfs(i);
dfs(1,0);
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
int u,v;
scanf("%d%d",&u,&v);
printf("%lld\n",qry(u,v));
}
}
int main(){
int t;
scanf("%d",&t);
while(t--)solve();
return 0;
}