poj 3728 tarjan+带权路径并查集

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=55009;
int n,q,a,b,fa[N],vis[N],ans[N],v[N],Max[N],Min[N],up[N],down[N];
vector<int> need[N],edge[N],kv[N];
int find(int x)
{
    if(x==fa[x])return x;
    int y=fa[x];
    fa[x]=find(fa[x]);

    up[x]=max(Max[y]-Min[x],max(up[x],up[y]));
    down[x]=max(Max[x]-Min[y],max(down[x],down[y]));

    Max[x]=max(Max[y],Max[x]);
    Min[x]=min(Min[y],Min[x]);

    return fa[x];
}

void tarjan(int x)
{
    vis[x]=1;
    for(int i=0;i<need[x].size();i=i+2)
    {
        int y=need[x][i];
        if(vis[y])
        {
            int t=find(y),f=need[x][i+1];
            if(f>0)
            {
                kv[t].push_back(x);
                kv[t].push_back(y);
            }
            else
            {
                kv[t].push_back(y);
                kv[t].push_back(x);
            }
            kv[t].push_back(f>0?f:-f);
        }
    }
    for(int i=0;i<edge[x].size();i++)
    {
        int y=edge[x][i];
        if(!vis[y])
        {
            tarjan(y);
            fa[y]=x;
        }
    }
    for(int i=0;i<kv[x].size();i=i+3)
    {
        int a=kv[x][i],b=kv[x][i+1],f=kv[x][i+2];
        find(a);find(b);
        ans[f]=max(up[a],max(down[b],Max[b]-Min[a]));
    }
}
void init()
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
        vis[i]=0;
        need[i].clear();
        edge[i].clear();
        kv[i].clear();
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        Max[i]=v[i];
        Min[i]=v[i];
        up[i]=0;
        down[i]=0;
    }
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&a,&b);
        need[a].push_back(b);
        need[a].push_back(i);
        need[b].push_back(a);
        need[b].push_back(-i);
    }
    tarjan(1);
    for(int i=1;i<=q;i++)
    {
        printf("%d\n",ans[i]);
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
    }
}