poj_3728 The merchant

题目:

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

思路:

  • 树上倍增:
      考虑最后解的情况可以分为三种情况,1:买卖都在,2:买卖都在,3:在买,在卖。所以只要在倍增数组上记录最小值、最大值、向上走能得到的最大利润和向下能得到的最大利润即可。复杂度
  • 并查集和Tarjan求lca:
      对于每一对查询,也是考虑解的三种情况。在Tarjan求lca的过程中,把每一对查询扔到lca上。再在lca上扫描每一对查询,这是lca是并查集的根,所以可以直接在并查集上维护最小值、最大值、向上走能得到的最大利润和向下能得到的最大利润。复杂度可以看做

代码:

  • 树上倍增:
#include <cstdio>
#include <algorithm>
#define File(_) freopen(#_".in","r",stdin),freopen(#_".out","w",stdout)
#define inf 2100000000
#define MN 50005
#define max3(a,b,c) max(max(a,b),c)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
Link<MN,MN<<1,int> G;
int fa[MN][18],Down[MN][18],Up[MN][18],Max[MN][18],Min[MN][18];
int w[MN],dep[MN];
void dfs(int o,int f){
    fa[o][0]=f;dep[o]=dep[f]+1;
    Down[o][0]=Up[o][0]=0;
    Max[o][0]=Min[o][0]=w[o];
    EOR(k,G,o){
        int v=G[k];
        if(v==f)continue;
        dfs(v,o);
    }
}
int n;
void init(){
    for(int k=1;k<=16;k++)
        for(int o=1;o<=n;o++){
            fa[o][k]=fa[fa[o][k-1]][k-1];
            Max[o][k]=max(Max[o][k-1],Max[fa[o][k-1]][k-1]);
            Min[o][k]=min(Min[o][k-1],Min[fa[o][k-1]][k-1]);
            Up[o][k]=max3(Up[o][k-1],Up[fa[o][k-1]][k-1],Max[fa[o][k-1]][k-1]-Min[o][k-1]);
            Down[o][k]=max3(Down[o][k-1],Down[fa[o][k-1]][k-1],Max[o][k-1]-Min[fa[o][k-1]][k-1]);
        }
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int d=dep[u]-dep[v];
    for(int k=0;k<=16;k++)if(d>>k&1)
        u=fa[u][k];
    if(u==v)return u;
    for(int k=16;~k;k--)
        if(fa[u][k]!=fa[v][k])
            u=fa[u][k],v=fa[v][k];
    return fa[u][0];
}
struct Data{int Max,Min,Up,Down;};
Data jmp(int u,int d){
    Data ans=(Data){0,inf,0};
    for(int i=0;i<=16;i++)if(d>>i&1){
        tomax(ans.Up,Up[u][i]);
        tomax(ans.Down,Down[u][i]);
        tomax(ans.Up,Max[u][i]-ans.Min);
        tomax(ans.Down,ans.Max-Min[u][i]);
        tomin(ans.Min,Min[u][i]);
        tomax(ans.Max,Max[u][i]);
        u=fa[u][i];
    }
    return ans;
}
int query(int u,int v){
    int p=lca(u,v);
    Data d1=jmp(u,dep[u]-dep[p]+1),d2=jmp(v,dep[v]-dep[p]+1);
    return max3(d1.Up,d2.Down,d2.Max-d1.Min);
}
int main(){
    //File(tree);
    int Q;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",w+i);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        G.add(u,v);G.add(v,u);
    }
    dfs(1,0);init();
    scanf("%d",&Q);
    while(Q--){
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",query(u,v));
    }
    return 0;
}
  • 并查集和Tarjan求lca:
#include <vector>
#include <cstdio>
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define max3(a,b,c) max(a,max(b,c))
#define MN 50005
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
Link<MN,MN<<1,int> G;
struct Data{int Min,Max,Up,Down,fa;};
Data ufs[MN];
Data find(int x){
    if(x!=ufs[x].fa){
        Data tmp=find(ufs[x].fa);
        ufs[x].fa=tmp.fa;
        tomax(ufs[x].Up,max(tmp.Up,tmp.Max-ufs[x].Min));
        tomax(ufs[x].Down,max(tmp.Down,ufs[x].Max-tmp.Min));
        tomax(ufs[x].Max,tmp.Max);
        tomin(ufs[x].Min,tmp.Min);
    }
    return ufs[x];
}
#define Fa(x) find(x).fa
#define Min(x) find(x).Min
#define Max(x) find(x).Max
#define Up(x) find(x).Up
#define Down(x) find(x).Down
struct Ques{int u,id,flag;};
vector<Ques> Q[MN];
int ans[MN];
bool vis[MN];
struct Pair{int u,v,id;};
vector<Pair> par[MN];
void dfs(int o,int f){
    EOR(k,G,o){
        int v=G[k];
        if(v==f)continue;
        dfs(v,o);
    }
    FOR(k,0,(int)Q[o].size()-1){
        Ques q=Q[o][k];
        if(!vis[q.u])continue;
        if(q.flag)par[Fa(q.u)].push_back((Pair){q.u,o,q.id});
        else par[Fa(q.u)].push_back((Pair){o,q.u,q.id});
    }
    FOR(k,0,(int)par[o].size()-1){
        Pair x=par[o][k];
        ans[x.id]=max3(Up(x.u),Down(x.v),Max(x.v)-Min(x.u));
    }
    vis[o]=1;
    ufs[o].fa=f;
}
int main(){
    int n,m;
    scanf("%d",&n);
    FOR(i,1,n){
        int x;
        scanf("%d",&x);
        ufs[i]=(Data){x,x,0,0,i};
    }
    FOR(i,1,n-1){
        int u,v;
        scanf("%d%d",&u,&v);
        G.add(u,v);G.add(v,u);
    }
    scanf("%d",&m);
    FOR(i,1,m){
        int a,b;
        scanf("%d%d",&a,&b);
        Q[a].push_back((Ques){b,i,0});
        Q[b].push_back((Ques){a,i,1});
    }
    dfs(1,0);
    FOR(i,1,m)printf("%d\n",ans[i]);
    return 0;
}