poj 3728 tarjan+带权路径并查集

[cpp]
#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);   www.2cto.com
    for(int i=1;i<=q;i++) 
    { 
        printf("%d/n",ans[i]); 
    } 
} 
int main() 
{ 
    while(scanf("%d",&n)!=EOF) 
    { 
        init(); 
    } 
} 
作者：wsniyufang