The merchant

Time Limit : 6000/3000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 1 Accepted Submission(s) : 1

Problem 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 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.

Input

<div>The first line contains N, the number of cities. Each of the next N lines contains wi the goods' price in each city. Each of the next N-1 lines contains labels of two cities, describing a road 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 a path. The cities are numbered from 1 to N. 1 ≤ N, wi, Q ≤ 50000

Output

<div>The output contains Q lines, each contains the maximum 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 0 0 0 0 2 0

Source

PKU

题目大意

　　有一棵树，每个结点有一个物品的价值。有一些询问，问在从一个点到另一个点了路径上，先在一个地方买，再在一个地方卖的最大获利。

解题思路

　　令从u

　　用离线Tarjan实现时在并查集路径压缩时进行DP，用倍增实现时直接在倍增数组上进行DP。

离线Tarjan写法

用的方法是离线LCA，在上面加了一些东西

对于一个询问，假设u,v的LCA是f

那么有三种可能，一个是从u到f 买卖了。一个是从f到v买卖了，一个是从u到f之间买了,从v到f卖了

从u到f 我们称为up，从f到v我们称为down，而从u到f买然后在f到v卖就是求u到f的最小值和f到v的最大值。

我们要分别求这三个值

实际上就是在离线tarjan求LCA的过程中求出的

对于每个点，我们进行dfs的时候，查看于其相关的询问，

假设当前点是u，询问的点是v， u和v的LCA是f,如果v已经dfs过了，说明v在并查集中的祖先就是u,v的LCA f点，

将该询问加入到f的相关集合中，等f所有的子节点都处理过后再去处理f，就可以发现，一切都是顺其自然了

在这些处理过程中，up和down以及u,v到f的最大值最小值都可以在并查集求压缩路径的过程中更新。

#include 
       
          #include 
        
           #include 
         
            #include 
          
             #include 
           
              #include 
            
              #include 
             
               #include 
               #include 
               
                 #define MAXN 52222 #define MAXM 222222 #define INF 1000000001 using namespace std; vector
                
                 g[MAXN], st[MAXN], ed[MAXN], id[MAXN], ask[MAXN], pos[MAXN]; int mx[MAXN], mi[MAXN], up[MAXN], down[MAXN], vis[MAXN], fa[MAXN], ans[MAXN]; int n, Q; int find(int x) { if(x == fa[x]) return x; int y = fa[x]; fa[x] = find(y); up[x] = max(up[x], max(mx[y] - mi[x], up[y])); down[x] = max(down[x], max(mx[x] - mi[y], down[y])); mx[x] = max(mx[x], mx[y]); mi[x] = min(mi[x], mi[y]); return fa[x]; } void tarjan(int u) { vis[u] = 1; for(int i = 0; i < ask[u].size(); i++) { int v = ask[u][i]; if(vis[v]) { int t = find(v); int z = pos[u][i]; if(z > 0) { st[t].push_back(u); ed[t].push_back(v); id[t].push_back(z); } else { st[t].push_back(v); ed[t].push_back(u); id[t].push_back(-z); } } } for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(!vis[v]) { tarjan(v); fa[v] = u; } } for(int i = 0; i < st[u].size(); i++) { int a = st[u][i]; int b = ed[u][i]; int t = id[u][i]; find(a); find(b); ans[t] = max(up[a], max(down[b], mx[b] - mi[a])); } } int main() { scanf("%d", &n); int u, v, w; for(int i = 1; i <= n; i++) { scanf("%d", &w); mx[i] = mi[i] = w; fa[i] = i; } for(int i = 1; i < n; i++) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } scanf("%d", &Q); for(int i = 1; i <= Q; i++) { scanf("%d%d", &u, &v); ask[u].push_back(v); pos[u].push_back(i); ask[v].push_back(u); pos[v].push_back(-i); } tarjan(1); for(int i = 1; i <= Q; i++) printf("%d\n", ans[i]); return 0; }

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define INF 0x3f3f3f3f#define fi first#define se secondconst int MAXN=50000+3;int V, Q, val[MAXN];vector
                
                  G[MAXN];vector
                 
                  
                    > q[MAXN];// id, othervector
                   
                    
                      > ans[MAXN];// to, itint up[MAXN], down[MAXN];//当前点到lca的最大获利，lca到当前点点最大获利int max_val[MAXN], min_val[MAXN];//当前点到lca的最大／最小价格int par[MAXN];bool vis[MAXN];int res[MAXN];int findfather(int x)//并查集查询，同时进行dp{ if(par[x]==x) return x; int fa=par[x]; par[x]=findfather(par[x]); up[x]=max(up[x], max(up[fa], max_val[fa]-min_val[x])); down[x]=max(down[x], max(down[fa], max_val[x]-min_val[fa])); max_val[x]=max(max_val[x], max_val[fa]); min_val[x]=min(min_val[x], min_val[fa]); return par[x];}void tarjan(int u){ par[u]=u; vis[u]=true; for(int i=0;i

View Code

倍增写法

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define INF 0x3f3f3f3f#define ULL unsigned long long#define LL long long#define fi first#define se second#define mem(a, b) memset((a),(b),sizeof(a))#define sqr(x) ((x)*(x))const int MAXN=50000+3;const int MAXLOG=17;int N, Q, price[MAXN];vector
                    
                      G[MAXN];int dp_max[MAXLOG][MAXN], dp_min[MAXLOG][MAXN];//向上走2^k步之间的最高与最低价格int dp_up[MAXLOG][MAXN], dp_down[MAXLOG][MAXN];//从u向上走2^k／向下走2^k步到u 的最大利润int parent[MAXLOG][MAXN];//向上走2^k步到达的点（超过根时记为-1）int depth[MAXN];void dfs(int u, int fa, int deep){ parent[0][u]=fa; depth[u]=deep; dp_up[0][u]=max(price[fa]-price[u], 0); dp_down[0][u]=max(price[u]-price[fa], 0); dp_max[0][u]=max(price[u], price[fa]); dp_min[0][u]=min(price[u], price[fa]); for(int i=0;i
                     
                      depth[v]) swap(u, v); for(int k=0;k
                      
                       >k&1) v=parent[k][v]; if(u==v) return u; for(int k=MAXLOG-1;k>=0;--k) if(parent[k][u]!=parent[k][v]) { u=parent[k][u]; v=parent[k][v]; } return parent[0][u];}int up(int u, int k, int &the_min){ the_min=INF; int res=0, pre_min_price=INF; for(int i=MAXLOG-1;i>=0;--i) if(k>>i&1) { the_min=min(the_min, dp_min[i][u]); res=max(res, dp_up[i][u]); res=max(res, dp_max[i][u]-pre_min_price); pre_min_price=min(pre_min_price, dp_min[i][u]); u=parent[i][u]; } return res;}int down(int u, int k, int &the_max){ the_max=0; int res=0, pre_max_price=0; for(int i=MAXLOG-1;i>=0;--i) if(k>>i&1) { the_max=max(the_max, dp_max[i][u]); res=max(res, dp_down[i][u]); res=max(res, pre_max_price-dp_min[i][u]); pre_max_price=max(pre_max_price, dp_max[i][u]); u=parent[i][u]; } return res;}int main(){ scanf("%d", &N); for(int i=0;i

View Code

转载于:https://www.cnblogs.com/caiyishuai/p/8605898.html

你可能感兴趣的文章