poj3728The merchant
The merchant
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 4800 | Accepted: 1666 |
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n,a[],head[],to[],nextt[],tot,q,d[];
int fa[][], minn[][], maxx[][], lmax[][], rmin[][]; void add(int x, int y)
{
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++;
} void dfs(int u, int from,int dist)
{
d[u] = dist;
fa[u][] = from;
for (int i = head[u]; i != -; i = nextt[i])
{
int v = to[i];
if (from != v)
dfs(v, u,dist + );
}
} void init()
{
dfs(, , );
minn[][] = maxx[][] = a[];
lmax[][] = - << ;
rmin[][] = << ;
for (int i = ; i <= n; i++)
{
minn[i][] = min(a[i], a[fa[i][]]);
maxx[i][] = max(a[i], a[fa[i][]]);
lmax[i][] = max(a[fa[i][]] - a[i], );
rmin[i][] = min(a[fa[i][]] - a[i], );
}
for (int j = ; ( << j) < n; j++)
for (int i = ; i <= n; i++)
{
fa[i][j] = fa[fa[i][j - ]][j - ];
maxx[i][j] = max(maxx[i][j - ], maxx[fa[i][j - ]][j - ]);
minn[i][j] = min(minn[i][j - ], minn[fa[i][j - ]][j - ]);
lmax[i][j] = max(max(lmax[i][j - ], lmax[fa[i][j - ]][j - ]), maxx[fa[i][j-]][j - ] - minn[i][j - ]);
rmin[i][j] = min(min(rmin[i][j - ], rmin[fa[i][j - ]][j - ]), minn[fa[i][j - ]][j - ] - maxx[i][j - ]);
}
} int LCA(int x, int y)
{
int maxxx = , miny = , minx = a[x], maxy = a[y];
for (int i = ; i >= && d[x] != d[y]; i--)
{
if (abs(d[x] - d[y]) >= << i)
{
if (d[y] < d[x])
{
maxxx = max(max(maxxx, lmax[x][i]), maxx[x][i] - minx);
minx = min(minx, minn[x][i]);
x = fa[x][i];
}
else
{
miny = min(min(miny, rmin[y][i]), minn[y][i] - maxy);
maxy = max(maxy, maxx[y][i]);
y = fa[y][i];
}
}
}
if (x == y)
return max(max(maxxx, -miny), maxy - minx);
for (int i = ; i >= ;i--)
if (fa[x][i] != fa[y][i] && fa[x][i] && fa[y][i])
{
maxxx = max(max(maxxx, lmax[x][i]), maxx[x][i] - minx);
minx = min(minx, minn[x][i]);
x = fa[x][i]; miny = min(min(miny, rmin[y][i]), minn[y][i] - maxy);
maxy = max(maxy, maxx[y][i]);
y = fa[y][i];
}
maxxx = max(max(maxxx, lmax[x][]), maxx[x][] - minx);
minx = min(minx, minn[x][]);
miny = min(min(miny, rmin[y][]), minn[y][] - maxy);
maxy = max(maxy, maxx[y][]);
return max(max(maxxx, -miny), maxy - minx); } int main()
{
memset(head, -, sizeof(head));
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
for (int i = ; i <= n - ; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
init();
scanf("%d", &q);
while (q--)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", LCA(x, y));
} return ;
}
最新文章
- struts2获取web元素的方式和方法
- python setup.py uninstall
- PHP 魔术方法总结
- java_spring_依赖注入
- ms08-067
- Android 给Button加个监听
- VPS服务器利用WINSCP软件进行SFTP管理服务器文件
- 自定义GridControl编辑器
- Latex文件分别用Texwork和Winedt打开时,产生中文乱码的解决方法
- dede后台删除文章后台还有分页显示解决方法
- python 画广东省等压线图
- android -------- RecyclerView的可(多个Item水平,垂直)滚动列表的实现
- 使用githubpages主题NexT的语法
- MySQL建库建表
- Shark简介、部署及编译小结
- 『科学计算』科学绘图库matplotlib练习
- 面试题46:求1+2+ …… +n
- asp.net 导出 Excel 身份证格式显示格式问题
- PHP中die()、exit()、return的区别
- 基于指定文本的百度地图poi城市检索的使用(思路最重要)
热门文章
- ubuntu 18.04下 配置qt opencv的坑
- IntelliJ IDEA java设置程序运行时内存
- java中Integer和int的区别
- 01_8_Struts用DomainModel接收参数
- C++函数的默认参数补充
- 如何用纯 CSS 创作一台拍立得照相机
- MySQL中文转换成拼音的函数
- R-data.table
- C++中重载、覆盖和隐藏的区别,以及适用场景
- build.xml: 21: Class not found: javac1.8