记录编号	608218	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3919.坡伊踹	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	27.989 s
提交时间	2025-10-24 16:19:19	内存使用	52.94 MiB

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+10;
ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<48||c>57){
        if(c==45) f=-1;
        c=getchar();
    }
    while(c>=48&&c<=57){
        x=(x<<1)+(x<<3)+c-48;
        c=getchar();
    }
    return f*x;
}
ll bb;
ll n,Q,rt;
ll a[N];
struct node{
    ll to,nxt,val;
}e[N<<1];
ll h[N],tot;
void add(ll u,ll v,ll w){
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].nxt=h[u];
    h[u]=tot;
    return;
}
ll f[N][25],g[N][25];
ll dis[N],dep[N];
ll lg[N];
queue<ll> q;

void init(){
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    q.push(rt);
    dis[rt]=0;
    dep[rt]=1;
    
    ll u,v,w;
    
    while(q.size()){
        u=q.front();q.pop();
        
        // 初始化当前节点u的第0层（如果还没初始化）
        if(g[u][0] == 0) {
            g[u][0] = a[u];
        }
        
        // 预处理当前节点u的倍增数组
        for(int j=1;j<=bb;j++){
            if(f[u][j-1]) {
                f[u][j] = f[f[u][j-1]][j-1];
                g[u][j] = min(g[u][j-1], g[f[u][j-1]][j-1]);
            }
        }
        
        // 遍历邻居节点
        for(ll i=h[u];i;i=e[i].nxt){
            v=e[i].to;w=e[i].val;
            if(dep[v]) continue;
            
            dis[v] = dis[u] + w;
            dep[v] = dep[u] + 1;
            f[v][0] = u;
            g[v][0] = min(a[u], a[v]);
            
            q.push(v);
        }
    }
}

ll lca(ll x,ll y){
    if(dep[x]<dep[y]) swap(x,y);
    for(ll i=bb;i>=0;i--)
        if(f[x][i] && dep[f[x][i]]>=dep[y]) 
            x=f[x][i];
    if(x==y) return x;
    for(ll i=bb;i>=0;i--){
        if(f[x][i] && f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
bool check(ll u,ll v,ll k){
    ll p=lca(u,v);
    ll x=u,y=u,ans=a[u],kk;
    if(dis[u]-dis[p]>k){
        for(int i=bb;i>=0;i--) 
            if(f[x][i] && dis[u]-dis[f[x][i]]<=k) 
                x=f[x][i];
        y=u;
        ans=a[u];
        for(int i=bb;i>=0;i--){
            if(f[y][i] && dis[f[y][i]]>=dis[x]){
                ans=min(ans,g[y][i]);
                y=f[y][i];
            }
        }
        ans=min(ans,a[x]); 
    }
    else{
        kk=k-(dis[u]-dis[p]);
        x=v;
        for(int i=bb;i>=0;i--) 
            if(f[x][i] && dis[f[x][i]]-dis[p]>kk) 
                x=f[x][i];
        if(dis[x]-dis[p]>kk && f[x][0]) 
            x=f[x][0];
        ans=min(ans,a[x]);
        y=u;
        for(int i=bb;i>=0;i--){
            if(f[y][i] && dis[f[y][i]]>=dis[p]){
                ans=min(ans,g[y][i]);
                y=f[y][i];
            }
        }
        y=x;
        for(int i=bb;i>=0;i--){
            if(f[y][i] && dis[f[y][i]]>=dis[p]){
                ans=min(ans,g[y][i]);
                y=f[y][i];
            }
        }
    }
    return ans<=k;
}

ll solve(ll u,ll v){
    ll l=0,r=1e9,mid,ans=1e9;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(u,v,mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}

int main(){
	freopen("poitry.in","r",stdin);
	freopen("poitry.out","w",stdout);
    n=read();Q=read();
    bb=log(n)/log(2)+1;
    rt=1;
    for(int i=1;i<=n;i++) a[i]=read();
    ll u,v,w;
    for(int i=1;i<n;i++){
        u=read();v=read();w=read();
        add(u,v,w);add(v,u,w);
    }
    init();
    while(Q--){
        u=read();v=read();
        printf("%lld\n",solve(u,v));
    }
    return 0;
}