换根dp求助

#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define pr pair<int,int>
#define mk make_pair
#define ft first
#define sd second
#define eb emplace_back 
#define sz(x) ((int)edge[x].size())

const int N=2e5+10,LG=30;
const int inf=1e18+10;

int n,q,c[N];

vector<pr> edge[N];

void add(int u,int v,int w){
	edge[u].eb(v,w); 
}

int dp[N],g[N],dep[N];
int mx[LG][N],fa[LG][N],dis[LG][N];

void dfs_dp(int u,int ff){
	dp[u]=c[u];
	for(auto t:edge[u]){
		int v=t.ft,w=t.sd;
		if(v==ff) continue;
		dfs_dp(v,u);
		dp[u]=max(dp[u],dp[v]-(w<<1));
	}
}

void redfs_dp(int u,int ff,int d,int up){
	g[u]=max(dp[u],d-(up<<1)); 
	vector<int> pre,suf;
	pre.resize(sz(u)+2),suf.resize(sz(u)+2);
	pre[0]=suf[sz(u)+1]=0;
	for(int i=1;i<=sz(u);i++){
		auto t=edge[u][i-1];
		int v=t.ft,w=t.sd;
		pre[i]=pre[i-1];
		if(v==ff) continue;
		pre[i]=max(pre[i],dp[v]-(w<<1));
	}
	for(int i=sz(u);i;i--){
		auto t=edge[u][i-1];
		int v=t.ft,w=t.sd;
		suf[i]=suf[i+1];
		if(v==ff) continue;
		suf[i]=max(suf[i],dp[v]-(w<<1));
	}
	for(int i=1;i<=sz(u);i++){
		auto t=edge[u][i-1];
		int v=t.ft,w=t.sd;
		if(v==ff) continue;
		redfs_dp(v,u,max({pre[i-1],suf[i+1],d-(up<<1)}),w);
	}
}

void dfs_fa(int u,int ff){
	dep[u]=dep[fa[0][u]=ff]+1;
	mx[0][u]=g[u];
	for(int i=1;i<=__lg(dep[u]);i++){
		fa[i][u]=fa[i-1][fa[i-1][u]];
		mx[i][u]=max(mx[i-1][u],mx[i-1][fa[i-1][u]]);
		dis[i][u]=dis[i-1][u]+dis[i-1][fa[i-1][u]];
	} 
	for(auto t:edge[u]){
		int v=t.ft,w=t.sd;
		if(v==ff) continue;
		dis[0][v]=w;
		dfs_fa(v,u);
	}
}

int lca(int u,int v){
	int mx=-inf,dis=0;
	if(dep[u]<dep[v]){
		swap(u,v);
	}
	while(dep[u]>dep[v]){
		int lg=__lg(dep[u]-dep[v]);
		mx=max(::mx[lg][u],mx);
		dis+=::dis[lg][u];
		u=fa[lg][u];
	}
	if(u==v){
		mx=max(mx,::mx[0][u]);
		return mx-dis;
	}
	for(int i=__lg(dep[u]);~i;i--){
		if(fa[i][u]!=fa[i][v]){
			mx=max({mx,::mx[i][u],::mx[i][v]});
			dis+=::dis[i][u]+::dis[i][v];
			u=fa[i][u],v=fa[i][v];
		}
	} 
	mx=max({mx,::mx[1][u],::mx[1][v]});
	dis+=::dis[0][u]+::dis[0][v];
	return mx-dis;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>c[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_dp(1,0);
	redfs_dp(1,0,0,0);
//	for(int i=1;i<=n;i++){
//		dfs_dp(i,0);
//		mx[0][i]=dp[i];
//		memset(dp,0,sizeof(dp)); 
//	}
	dfs_fa(1,0);
	while(q--){
		int u,v; cin>>u>>v;
		cout<<c[u]+c[v]+lca(u,v)<<'\n';
	} 
	return 0;
}