记录编号	608230	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3919.坡伊踹	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	19.194 s
提交时间	2025-10-24 18:06:39	内存使用	45.38 MiB

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 2 * 1e5 + 5;
const int LOG = 20;

int n, q;
int fa[MAXN][LOG];
int minx[MAXN][LOG];
int a[MAXN];
struct node{
	int to, next, len;
}e[2 * MAXN];
int dep[MAXN], dis[MAXN];
int h[MAXN], tot = 0;

void add(int x, int y, int len){
	e[++ tot] = {y, h[x], len};
	h[x] = tot;
}

void dfs(int u, int f){
	dep[u] = dep[f] + 1;
	fa[u][0] = f;
	minx[u][0] = (f == 0) ? a[u] : min(a[u], a[f]);
	for(int i = h[u];i;i = e[i].next){
		int v = e[i].to, w = e[i].len;
		if(v == f) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

void Init(){
	for(int k = 1;k < LOG;k ++){
		for(int u = 1;u <= n;u ++){
			fa[u][k] = fa[fa[u][k - 1]][k - 1];
			minx[u][k] = min(minx[u][k - 1], minx[fa[u][k - 1]][k - 1]);
		}
	}
}

int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int k = LOG - 1;k >= 0;k --){
		if(dep[fa[u][k]] >= dep[v]){
			u = fa[u][k];
		}
	}
	if(u == v) return u;
	for(int k = LOG - 1;k >= 0;k --){
		if(fa[u][k] != fa[v][k]){
			u = fa[u][k];
			v = fa[v][k];
		}
	}
	return fa[u][0];
}

bool check(int u, int v, int lc, int k){
    int mn = a[u], x = u, y = v;
    // u -> lc
    for(int i = LOG - 1;i >=0;i --){
        int anc = fa[x][i];
        if(dep[anc] >= dep[lc] && dis[u] - dis[anc] <= k){
            mn = min(mn, minx[x][i]);
            x=anc;
        }
    }
    // v -> lc
    for(int i = LOG - 1;i >= 0;i --){
        int anc = fa[y][i];
        if(dep[anc] >= dep[lc] && dis[u] - dis[lc] + dis[anc] - dis[lc] > k)
            y = anc;
    }
    if(dis[u] - dis[lc] + dis[y] - dis[lc] > k) y = fa[y][0];
    for(int i = LOG - 1;i >= 0;i --){
        int anc = fa[y][i];
        if(dep[anc] >= dep[lc]){
            mn = min(mn, minx[y][i]);
            y = anc;
        }
    }
    return mn <= k;
}

signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n >> q;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	for(int i = 1;i < n;i ++){
		int u, v, w; cin >> u >> v >> w;
		add(u, v, w); add(v, u, w);
	}
	dfs(1, 0);
	Init();
	for(int i = 1;i <= q;i ++){
		int u, v; cin >> u >> v;
		int LCA = lca(u, v);
		int l = 0, r = 1e9;
		while(l < r){
			int mid = (l + r) >> 1;
			if(check(u, v, LCA, mid)){
				r = mid;
			}
			else l = mid + 1;
		}
		cout << l << '\n';
	}
	return 0;
}