C++14(g++5.4) 解法, 执行用时: 155ms, 内存消耗: 14232K, 提交时间: 2020-02-21 16:04:30

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e4+88;
vector<int>G[N],Q[N],dir[N],st[N],ed[N],pos[N];
int m,F[N],ans[N],mx[N],mi[N],up[N],down[N],n,W[N];
bool vis[N];
int find(int x){
    if(F[x]==x) return x;
    int t=find(F[x]);
    
    up[x]=max(max(up[x],up[F[x]]),mx[F[x]]-mi[x]);
    down[x]=max(max(down[x],down[F[x]]),mx[x]-mi[F[x]]);
    mi[x]=min(mi[F[x]],mi[x]);
    mx[x]=max(mx[F[x]],mx[x]);
    
    return F[x]=t;
}
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<(int)Q[u].size();++i) {
        int v=Q[u][i];
        if(vis[v]) {
            int t=find(v),z=dir[u][i];
            if(z>0) {
                st[t].push_back(u);
                ed[t].push_back(v);
                pos[t].push_back(z);
            }
            else {
                st[t].push_back(v);
                ed[t].push_back(u);
                pos[t].push_back(-z);
            }
        }
    }
    for(int i=0;i<(int)G[u].size();++i) if(!vis[G[u][i]])
    dfs(G[u][i]),F[G[u][i]]=u;
    for(int i=0;i<(int)st[u].size();++i) {
        int x=st[u][i],y=ed[u][i],z=pos[u][i];
        find(x);find(y);
        ans[z]=max(mx[y]-mi[x],max(up[x],down[y]));
    }
}
int main(){
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",W+i);
    for(int i=1;i<=n;++i) F[i]=i,mx[i]=mi[i]=W[i];
    for(int i=1;i<n;++i) {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&x,&y);
        Q[x].push_back(y);
        dir[x].push_back(i);
        Q[y].push_back(x);
        dir[y].push_back(-i);
    }
    dfs(1);
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
}

C++ 解法, 执行用时: 70ms, 内存消耗: 14128K, 提交时间: 2021-07-28 19:36:45

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e5+7;
int n,m,mn[N],mx[N],up[N],down[N],ans[N],fa[N];
int vis[N];
struct node{
	int s,t,id;
};
vector<node> g[N],q[N],e[N];
int Find(int x){
	if(fa[x]==x) return x;
	int root=Find(fa[x]);
	up[x]=max(max(up[x],up[fa[x]]),mx[fa[x]]-mn[x]);
	down[x]=max(max(down[x],down[fa[x]]),mx[x]-mn[fa[x]]);
	mn[x]=min(mn[x],mn[fa[x]]);
	mx[x]=max(mx[x],mx[fa[x]]);
	return fa[x]=root;
}
void dfs(int u){
	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		node v=g[u][i];
		if(!vis[v.s]){
			dfs(v.s);
			fa[v.s]=u;
		}
	}
	for(int i=0;i<q[u].size();i++){
		node v=q[u][i];
		if(vis[v.s]){
			int lca=Find(v.s);
			if(v.id>0) e[lca].push_back({u,v.s,v.id});
			else e[lca].push_back({v.s,u,-v.id});
		}
	}
	for(int i=0;i<e[u].size();i++){
		node v=e[u][i];
		int x=v.s,y=v.t,id=v.id;
		Find(x);
		Find(y);
		ans[id]=max(mx[y]-mn[x],max(up[x],down[y]));
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int w;
		scanf("%d",&w);
		mn[i]=mx[i]=w;
		fa[i]=i;
	}
	int a,b;
	node v;
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		v.s=b;
		g[a].push_back(v);
		v.s=a;
		g[b].push_back(v);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int s,t;
		scanf("%d%d",&s,&t);
		v.s=t;
		v.id=i;
		q[s].push_back(v);
		v.s=s;
		v.id=-i;
		q[t].push_back(v);
	}
	dfs(1);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}