求条代码

/*
1.Binary Search?
2.Dynamic Program?
3.Data Structure?
4.Monotonic?
5.Modulo?
6.Tarjan?
7.Offline?
8.ChthollyTree? (Mo's Algorithm?)
9.SimulateAnneal? (That's not possible)



1.Think Backward?
2.Make Charts?
3.Find Features?
4.Widen Constraints?
5.Answer = All - Illegal
6.Skip the process.Focus on the result
*/
#include<bits/stdc++.h>

#define int long long

using namespace std;

constexpr int inf = 1e18;

int n = 0 , T = 0 , q = 0 , cnt = 0 , dfs_time = 0;

array<int , 200100> head , son , top , dep , up , sizes , dfn , len;

array<int , 3000100> Log;

array<int , 30> pre;

array<bool , 100100> tag , vis;

array<array<int , 100100> , 25> dis;

array<array<array<int , 2> , 100100> , 25> dp;

struct Node{
	int to;
	int nxt;
	int val;
};

array<Node , 400100> edge;

struct Lilies{
	int s;
	int t;
	int ans;
};

array<Lilies , 400100> quest;

priority_queue<pair<int , int> , vector<pair<int , int> > , greater<pair<int , int> > > que;

void new_line(int a , int b , int c)
{
	edge[++ cnt].to = b;
	edge[cnt].nxt = head[a];
	edge[cnt].val = c;
	head[a] = cnt;
	
	return;
}

int get_lca(int x , int y)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]]) swap(x , y);
		x = up[top[x]];
	}
	
	return dep[x] > dep[y] ? y : x;
}

int calc(int id , int x , int y)
{
	int LCA = get_lca(x , y);
	return dis[id][x] + dis[id][y] - 2 * dis[id][LCA];
}

int ask(int id , int l , int r)
{
	int base = Log[r - l + 1];
	
	return min(dp[base][l][id] , dp[base][r - pre[base] + 1][id]);
}

int query(int id , int x , int LCA)
{
	int res = inf;
	
	while(top[x] != top[LCA])
	{
		res = min(res , ask(id , dfn[top[x]] , dfn[x]));
		x = up[top[x]];
	}
	
	return min(res , ask(id , dfn[LCA] , dfn[x]));
}

void dfs1(int x , int fa)
{
	dep[x] = dep[fa] + 1;
	sizes[x] = 1 , up[x] = fa;
	
	for(int e = head[x];e;e = edge[e].nxt)
	{
		int to = edge[e].to;
		
		if(to == fa) continue;
		
		int val = edge[e].val << 1;
		
		for(int j = 0;j <= 21;++ j) dis[j][to] = dis[j][x] + (val = (val + 1) >> 1);
		
		dfs1(to , x);
		
		sizes[x] += sizes[to];
		
		if(!son[x] || sizes[son[x]] < sizes[to]) son[x] = to;
	}
	
}
void dfs2(int x , int tmp)
{
	top[x] = tmp;
	dfn[x] = ++ dfs_time;
	
	if(son[x]) dfs2(son[x] , tmp);
	
	for(int e = head[x];e;e = edge[e].nxt)
	{
		int to = edge[e].to;
		
		if(to != up[x] && to != son[x]) dfs2(to , to);
	}
	
	return;
}
void precalc(int lv)
{
	for(int i = 1;i <= n;++ i)
	{
		len[i] = tag[i] ? 0 : inf , vis[i] = 0;
		
		if(tag[i]) que.push({len[i] , i});
	}
	
	while(!que.empty())
	{
		int x = que.top().second;
		
		que.pop();
		
		if(vis[x]) continue;
		
		vis[x] = 1;
		
		for(int e = head[x];e;e = edge[e].nxt)
		{
			int to = edge[e].to , val = edge[e].val;
			
			if(len[to] > len[x] + val + ((val - 1) / pre[lv]) + 1)
			{
				len[to] = len[x] + val + ((val - 1) / pre[lv]) + 1;
				que.push({len[to] , to});
			}
		}
		
	}
	for(int i = 1;i <= n;++ i)
	{
		dp[0][dfn[i]][0] = len[i] + dis[lv][i] - dis[0][i];
		dp[0][dfn[i]][1] = len[i] - dis[lv][i] + dis[0][i];
	}
	
	for(int i = 1;i <= 21;++ i) for(int j = 1;j + pre[i] - 1 <= n;++ j) for(auto it : {0 , 1}) dp[i][j][it] = min(dp[i - 1][j][it] , dp[i - 1][j + pre[i - 1]][it]);
	
	return;
}

signed main()
{
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	pre[0] = 1;
	
	for(int i = 1;i <= 21;++ i) pre[i] = pre[i - 1] << 1;
	for(int i = 2;i <= 3e6;++ i) Log[i] = Log[i >> 1] + 1;
	
	int test = 0;
	
	cin >> test;
	
	while(test --)
	{	
		cnt = dfs_time = 0;
		
		cin >> n >> T;
		
		for(int i = 1;i <= n;++ i) head[i] = son[i] = dep[i] = sizes[i] = 0;
		
		for(int i = 1;i < n;++ i)
		{
			int x = 0 , y = 0 , c = 0;
			
			cin >> x >> y >> c;
			
			new_line(x , y , c);
			new_line(y , x , c);
		}
		
		for(int i = 1;i <= n;++ i)
		{
			char ch;
			
			cin >> ch;
			
			tag[i] = ch - '0';
		}
		
		dfs1(1 , 1);
		dfs2(1 , 1);
		
		cin >> q;
		
		for(int i = 1;i <= q;++ i)
		{
			cin >> quest[i].s >> quest[i].t;
			
			quest[i].ans = calc(0 , quest[i].s , quest[i].t);
		}
		
		for(int i = 1;i <= 21;++ i)
		{
			precalc(i);
			
			for(int x = 1;x <= q;++ x)
			{
				int a = quest[x].t , b = quest[x].s;
				
				int LCA = get_lca(a , b);
				
				quest[x].ans = min(quest[x].ans , i * T + dis[0][a] + query(0 , a , LCA) - dis[i][LCA] + dis[i][b] - dis[i][LCA]);
				quest[x].ans = min(quest[x].ans , i * T + dis[0][a] - dis[0][LCA] + query(1 , b , LCA) - dis[0][LCA] + dis[i][b]);
			}
		}
		
		for(int i = 1;i <= q;++ i) cout << quest[i].ans << '\n'; 
	}
	
	cout << endl;
	
	return 0;
}