POJ 3728 The merchant

The merchant

Time Limit: 3000MS	Memory Limit: 65536K
Total Submissions: 4773	Accepted: 1654

Description

There are N cities in a country, and there is one and only one simple path between each pair of cities. A merchant has chosensome paths and wants to earn as much money as possible in each path. When hemove along a path, he can choose one city to buy some goods and sell them in acity after it. The goods in all cities are the same but the prices aredifferent. Now your task is to calculate the maximum possible profit on eachpath.

Input

The first line contains N, the number ofcities.

Each of the next N lines containswi the goods' pricein each city.

Each of the next N-1 lines contains labels of two cities, describing aroad between the two cities.

The next line contains Q, the number of paths.

Each of the next Q lines contains labels of two cities, describing apath. The cities are numbered from 1 toN.

1 ≤ N,wi,Q ≤ 50000

Output

The output contains Q lines, each contains themaximum profit of the corresponding path. If no positive profit can be earned,output 0 instead.

Sample Input

4

1

5

3

2

1 3

3 2

3 4

9

1 2

1 3

1 4

2 3

2 1

2 4

3 1

3 2

3 4

Sample Output

4

2

2

2

題意：有n個城市，給出一件貨物在各城市的價格，并給出各城市間的連接配接關系(共n-1條邊，即構成一棵生成樹)，然後給出q個詢問，每個詢問有兩個城市s,t，問從s到t的路徑上買入賣出貨物盈利的最大值(顯然，要是變大，我們應該選擇在價格低的地方買入，價格高的地方賣出)。

思路：我們用幾個數組來維護以下值：

• 用up數組維護從目前點到目前根節點的最大盈利。
• 用down數組維護目前的wasd根節點到目前點的最大盈利。
• 用Max數組維護目前點到目前根節點的最大價格。
• 用Min數組維護目前點到目前根節點的最小價格。

實作方法依然是LCA的Tarjan算法，以上維護在并查集時實作。

LCA算法簡介：傳送門

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define f(i,a,b) for(int i=(a);i<(b);++i)
typedef long long ll;
const int maxn= 100005;
const int mod = 475;
const ll INF = 0x3f3f3f3f;
const double eps = 1e-6;
#define rush() int T;scanf("%d",&T);while(T--)

int n,m,cnt,cnt2;
int pre[maxn];
int vis[maxn];
int head1[maxn],head2[maxn],head3[maxn];
int up[maxn],down[maxn],Max[maxn],Min[maxn];
int val[maxn],ans[maxn];


struct node
{
    int s,t,next;
}e1[maxn*2],e2[maxn*2];

struct node2
{
    int k,next;
}e3[maxn*2];

void init()
{
    cnt2=0;
    mst(vis,0);
    mst(ans,0);
    mst(head1,-1);
    mst(head2,-1);
    mst(head3,-1);
    for(int i=0;i<=n;i++)
        pre[i]=i;
}
void add1(int s,int t)
{
    e1[cnt].s=s;
    e1[cnt].t=t;
    e1[cnt].next=head1[s];
    head1[s]=cnt++;
}

void add2(int s,int t)
{
    e2[cnt].s=s;
    e2[cnt].t=t;
    e2[cnt].next=head2[s];
    head2[s]=cnt++;
}

void add3(int u,int k)
{
    e3[cnt2].k=k;
    e3[cnt2].next=head3[u];
    head3[u]=cnt2++;
}

int find(int x)
{
    if(x==pre[x])
        return x;
    int fa=pre[x];
    pre[x]=find(pre[x]);
    up[x]=max(up[x],max(up[fa],Max[fa]-Min[x]));
    down[x]=max(down[x],max(down[fa],Max[x]-Min[fa]));
    Max[x]=max(Max[x],Max[fa]);
    Min[x]=min(Min[x],Min[fa]);
    return pre[x];
}

void join(int a,int b)
{
    int A,B;
    A=find(a);
    B=find(b);
    if(A!=B)
        pre[B]=A;
}


void Tarjan(int now)
{
    vis[now]=1;
    for(int i=head1[now];i!=-1;i=e1[i].next)
    {
        int t=e1[i].t;
        if(vis[t]==0)
        {
            Tarjan(t);
            join(now,t);
        }
    }
    for(int i=head2[now];i!=-1;i=e2[i].next)
    {
        int t=e2[i].t;
        if(vis[t]==1)
        {
            int lca=find(t);
            add3(lca,i);
        }
    }
    for(int i=head3[now];i!=-1;i=e3[i].next)
    {
        int k=e3[i].k;
        int s=e2[k].s;
        int t=e2[k].t;
        if(k&1)              //k--;
        {
            k^=1;
            swap(s,t);      //如果是反向邊要交換起點和終點
        }
        k/=2;
        find(s);
        find(t);
        ans[k]=max(Max[t]-Min[s],max(up[s],down[t]));
    }
}

int main()
{
    int x;
    int u,v;
    while(~scanf("%d",&n))
    {
        init();
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            up[i]=down[i]=0;
            Max[i]=Min[i]=x;
        }
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            add1(u,v);
            add1(v,u);
        }
        cnt=0;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            add2(u,v);
            add2(v,u);
        }
        Tarjan(1);
        for(int i=0;i<m;i++)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}