记录编号	583535	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	坡伊踹	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.322 s
提交时间	2023-10-18 12:09:39	内存使用	226.99 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

constexpr int maxn = 1e6 + 5;
constexpr i64 inf = 1e16;
int n, q, lg[maxn], dep[maxn], fa[maxn], siz[maxn], son[maxn], top[maxn], dfn[maxn], idfn[maxn], dfc;
std::vector<pii> G[maxn];
i64 d[maxn], a[maxn], st[20][maxn];

void dfs1(int u, int ff) {
	fa[u] = ff; dep[u] = dep[ff] + 1; siz[u] = 1;
	for(auto& [v, w] : G[u]) {
		if(v == ff) continue ;
		d[v] = d[u] + w;
		dfs1(v, u); siz[u] += siz[v]; 
		if(siz[v] > siz[son[u]]) son[u] = v;
	}
	return ;
}
void dfs2(int u, int tp) {
	top[u] = tp; dfn[u] = ++ dfc; idfn[dfc] = u;
	if(!son[u]) return ;
	dfs2(son[u], tp);
	for(auto& [v, w] : G[u])
		if(v != fa[u]&&v != son[u]) dfs2(v, v);
	return ;
}
int LCA(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
std::vector<pii> climb(int u, int tar) {
	std::vector<pii> A;
	while(top[u] != top[tar])
		A.pb(dfn[top[u]], dfn[u]), u = fa[top[u]];
	A.pb(dfn[tar], dfn[u]);
	return A;
}
i64 qry(int l, int r) {
	if(l > r) return inf;
	int k = lg[r - l + 1];
	return std::min(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
	freopen("poitry.in", "r", stdin);
	freopen("poitry.out", "w", stdout);
	scanf("%d %d", &n, &q);
	for(int i = 1;i <= n;++ i)
		scanf("%lld", &a[i]);
	for(int i = 2;i <= n;++ i) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		G[u].pb(v, w); G[v].pb(u, w);
		lg[i] = lg[i >> 1] + 1;
	}
	dfs1(1, 0); dfs2(1, 1); 
	for(int i = 1;i <= n;++ i)
		st[0][i] = a[idfn[i]];
	for(int k = 1;k <= lg[n];++ k)
		for(int i = 1;i + (1 << k) - 1 <= n;++ i)
			st[k][i] = std::min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
	while(q --) {
		int u, v; scanf("%d %d", &u, &v);
		int t = LCA(u, v);
		std::vector<pii> pth1 = climb(u, t), pth2 = climb(v, t);
		std::reverse(pth2.begin(), pth2.end());
		bool tar = false;
		i64 cur = inf, ans = inf;
		for(auto& [ql, qr] : pth1) {
			i64 lst = cur;
			cur = std::min(cur, (i64)qry(ql, qr));
			if(cur >= d[u] - d[idfn[ql]]) {
				ans = std::min(ans, cur);
			} else {
				int l = ql, r = qr; cur = lst; // qr -> ql
				while(l <= r) {
					int mid = (l + r) >> 1, x = idfn[mid];
					if(std::min(lst, qry(mid, qr)) >= d[u] - d[x]) {
						r = mid - 1;
					} else {
						l = mid + 1;
					}
				}
				ans = std::min(ans, qry(l, qr));
				ans = std::min(ans, d[u] - d[idfn[l - 1]]);
				tar = true; break ;
			}
		}
		if(tar) { printf("%lld\n", ans); continue ; }
		for(auto& [ql, qr] : pth2) {
			i64 lst = cur;
			cur = std::min(cur, qry(ql, qr));
			if(cur >= d[u] - 2 * d[t] + d[idfn[qr]]) {
				ans = std::min(ans, cur);
			} else {
				int l = ql, r = qr; cur = lst; // ql -> qr
				while(l <= r) {
					int mid = (l + r) >> 1, x = idfn[mid];
					if(std::min(lst, qry(ql, mid)) >= d[u] - 2 * d[t] + d[x]) {
						l = mid + 1;
					} else {
						r = mid - 1;
					}
				}
				ans = std::min(ans, qry(ql, r));
				ans = std::min(ans, d[u] - 2 * d[t] + d[idfn[r + 1]]);
				tar = true; break ;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}