poj 3728 The merchant(LCA)


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

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

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

POJ Monthly Contest – 2009.04.05, GaoYihan
转自:http://m.blog.csdn.net/blog/sdj222555/43003179

题意很简单

给一个树(n < 5w) 每个点有个权值,代表商品价格

若干个询问(5w)

对每个询问,问的是从u点走到v点(简单路径),商人在这个路径中的某点买入商品,然后在某点再卖出商品, 最大可能是多少

注意一条路径上只能买卖一次,先买才能卖

用的方法是离线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的最大值最小值 都可以在并查集求压缩路径的过程中更新。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <map>
 9 #include <ctime>
10 #define MAXN 52222
11 #define MAXM 222222
12 #define INF 1000000001
13 using namespace std;
14 vector<int>g[MAXN], st[MAXN], ed[MAXN], id[MAXN], ask[MAXN], pos[MAXN];
15 int mx[MAXN], mi[MAXN], up[MAXN], down[MAXN], vis[MAXN], fa[MAXN], ans[MAXN];
16 int n, Q;
17 int find(int x) {
18     if(x == fa[x]) return x;
19     int y = fa[x];
20     fa[x] = find(y);
21     up[x] = max(up[x], max(mx[y] - mi[x], up[y]));
22     down[x] = max(down[x], max(mx[x] - mi[y], down[y]));
23     mx[x] = max(mx[x], mx[y]);
24     mi[x] = min(mi[x], mi[y]);
25     return fa[x];
26 }
27 void tarjan(int u) {
28     vis[u] = 1;
29     for(int i = 0; i < ask[u].size(); i++) {
30         int v = ask[u][i];
31         if(vis[v]) {
32             int t = find(v);
33             int z = pos[u][i];
34             if(z > 0) {
35                 st[t].push_back(u);
36                 ed[t].push_back(v);
37                 id[t].push_back(z);
38             } else {
39                 st[t].push_back(v);
40                 ed[t].push_back(u);
41                 id[t].push_back(-z);
42             }
43         }
44     }
45     for(int i = 0; i < g[u].size(); i++) {
46         int v = g[u][i];
47         if(!vis[v]) {
48             tarjan(v);
49             fa[v] = u;
50         }
51     }
52     for(int i = 0; i < st[u].size(); i++) {
53         int a = st[u][i];
54         int b = ed[u][i];
55         int t = id[u][i];
56         find(a);
57         find(b);
58         ans[t] = max(up[a], max(down[b], mx[b] - mi[a]));
59     }
60 }
61 
62 int main() {
63         scanf("%d", &n);
64         int u, v, w;
65 
66         for(int i = 1; i <= n; i++) {
67             scanf("%d", &w);
68             mx[i] = mi[i] = w; fa[i] = i;
69         }
70         for(int i = 1; i < n; i++) {
71             scanf("%d%d", &u, &v);
72             g[u].push_back(v);
73             g[v].push_back(u);
74 
75         }
76         scanf("%d", &Q);
77         for(int i = 1; i <= Q; i++) {
78             scanf("%d%d", &u, &v);
79             ask[u].push_back(v);
80             pos[u].push_back(i);
81             ask[v].push_back(u);
82             pos[v].push_back(-i);
83         }
84         tarjan(1);
85         for(int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
86 
87     return 0;
88 }
View Code

优质内容筛选与推荐>>
1、centos构建face_recognition环境
2、Gitlab CI/CD任务一直处于pending
3、spring cloud详解
4、【转载】分页与分库那些事儿(线上交流纪要)
5、Scrapy 框架 总结


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn