#include<cstdio>
#include<cstring>
const int N=50005;
int n,m;
struct qq
{
	int x;
	int y;
	int last;
};
qq s[N*2];
qq s1[N*2];
qq s2[N*2];
int k[N];
int last[N];
int last1[N];
int last2[N];
int ans[N];
int num=0,num1=0;
int f[N];
bool p[N];
int up[N];
int down[N];
int max[N];
int min[N];
int Max (int x,int y){return x>y?x:y;}
int Min (int x,int y){return x<y?x:y;}
void init (int x,int y)
{
	num++;
	s[num].x=x;
	s[num].y=y;
	s[num].last=last[x];
	last[x]=num;
}
void init2 (int u,int k)
{
	num1++;
	s2[num1].x=k; 
	s2[num1].last=last2[u]; 
	last2[u]=num1;
}
void init1 (int x,int y,int z)
{
	s1[z].x=x;
	s1[z].y=y;
	s1[z].last=last1[x];
	last1[x]=z;
}

int find (int x)
{
	if (f[x]==x) return f[x];
	int fa1=f[x];
	f[x]=find(f[x]);
	up[x]=Max(up[x],Max(up[fa1],max[fa1]-min[x]));
	down[x]=Max(down[x],Max(down[fa1],max[x]-min[fa1]));
	max[x]=Max(max[x],max[fa1]);
	min[x]=Min(min[x],min[fa1]);
	return f[x];
}
void TJ (int x)
{
	for (int u=last1[x];u!=-1;u=s1[u].last)
		if (p[s1[u].y])
		{
			int lca=find(s1[u].y);
			init2(lca,u);
		}
	
	f[x]=x;
	p[x]=true;
	for (int u=last[x];u!=-1;u=s[u].last)
	{
		if (p[s[u].y]==false)
		{
			TJ(s[u].y);
			f[s[u].y]=x;
		}
	}
	for(int u=last2[x];u!=-1;u=s2[u].last)
    {
        int k=s2[u].x,x=s1[k].x,y=s1[k].y;
        if (k>m)
        {
        	k-=m;
        	int t1=x;x=y;y=t1;
    	}
        find(x); find(y);
        ans[k] = Max(up[x] , down[y]);
        ans[k] = Max(ans[k] , max[y] - min[x]);
    }
}
int main()
{
	while (scanf("%d",&n)!=EOF)
	{
	num=0;num1=0;
	memset(last2,-1,sizeof(last2));
	memset(p,false,sizeof(p));
	memset(last,-1,sizeof(last));
	memset(last1,-1,sizeof(last1));
	for (int u=1;u<=n;u++)
	{
		int a;
		scanf("%d",&a);
		max[u]=min[u]=a;
		up[u]=down[u]=0;
	}
	for (int u=1;u<n;u++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		init(x,y);
		init(y,x);
	}
	scanf("%d",&m);
	for (int u=1;u<=m;u++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		init1(x,y,u);
		init1(y,x,u+m);
	}
	TJ(1);
	for (int u=1;u<=m;u++) printf("%d\n",ans[u]);
	}
	return 0;
}

• Re:Tarjan离线，做了好久才做出来，纪念一下 (2402) OZY123 2016-01-05 13:20:57
  • Re:Tarjan离线，做了好久才做出来，纪念一下 (72) OZY123 2016-01-05 13:22:07
• Re:Tarjan离线，做了好久才做出来，纪念一下 (2402) zhangya656 2021-08-17 09:43:12