MX-S7-T2 Speaker题解

#include <bits/stdc++.h>
template <typename T>inline void read(T& aim){T num=0,f=1;int ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())num=num*10+ch-'0';aim=num*f;}
template <typename T>inline void write(T x){static int sta[40];int top=0;if(!x){putchar('0');return;}if(x<0)putchar('-'),x=-x;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top--]+'0');}
template <typename T>inline void print(T x,char ch=' '){write(x);putchar(ch);}
inline void nl(){putchar('\n');}
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N=2e5+9,M=4e5+9;

int head[N],ver[M],edge[M],nxt[M],tot;
void add(int x,int y,int z){
	ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}

int n,q,a[N];
LL mxw[N];
void dp(int x,int fa){
	mxw[x]=a[x];
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa)continue;
		dp(y,x);
		mxw[x]=max(mxw[x],mxw[y]-2*edge[i]);
	}
}
void dp2(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa)continue;
		mxw[y]=max(mxw[y],mxw[x]-2*edge[i]);
		dp2(y,x);
	}
}
int d[N],f[N][20],t;
LL dist[N],g[N][20];
queue<int> que;
void bfs(){
	d[1]=1;
	que.push(1);
	while(que.size()){
		int x=que.front();que.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(d[y])continue;
			d[y]=d[x]+1;dist[y]=dist[x]+edge[i];
			f[y][0]=x;g[y][0]=mxw[y];
			for(int j=1;j<=t;j++){
				f[y][j]=f[f[y][j-1]][j-1];
				g[y][j]=max(g[y][j-1],g[f[y][j-1]][j-1]);
			}
			que.push(y);//
		}
	}
}
pair<int,LL> lca(int x,int y){
	LL res=0;
	if(d[x]<d[y])swap(x,y);
	for(int i=t;i>=0;i--){
		if(d[f[x][i]]>=d[y]){
			res=max(res,g[x][i]);
			x=f[x][i];
		}
	}
	if(x==y){
		return {x,max(res,mxw[x])};
	}
	for(int i=t;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			res=max(res,g[x][i]);
			res=max(res,g[y][i]);
			x=f[x][i];y=f[y][i];
		}
	}
	res=max(res,g[x][0]);
	res=max(res,g[y][0]);
	return {f[x][0],max(res,mxw[f[x][0]])};
}
int main(){
	read(n);read(q);
	t=log2(n)+1;
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<n;i++){
		int x,y,z;read(x);read(y);read(z);
		add(x,y,z);add(y,x,z);
	}
	
	dp(1,0);dp2(1,0);
	bfs();
	for(int i=1;i<=q;i++){
		int x,y;read(x);read(y);
		pair<int,LL> res=lca(x,y);
		print(res.second+a[x]+a[y]-(dist[x]+dist[y]-2*dist[res.first]),'\n');
	}
	
	return 0;
}