网站建设需要提供哪些资料,男人和女人做哪个网站,网站建设全网营销客户资源,网站开发如何洽谈客户题目链接#xff1a;http://poj.org/problem?id3728 思路#xff1a;题目的意思是求树上a - b的路径上的最大收益#xff08;在最小值买入#xff0c;在最大值卖出#xff09;。 我们假设路径a - b 之间的LCA(a, b) f, 并且另up[a]表示a - f之间的最大收益… 题目链接http://poj.org/problem?id3728 思路题目的意思是求树上a - b的路径上的最大收益在最小值买入在最大值卖出。 我们假设路径a - b 之间的LCA(a, b) f, 并且另up[a]表示a - f之间的最大收益down[a]表示f - a之间的最大收益dp_max[a]表示a - f之间的最大值dp_min[a]表示a - f之间的最小值于是可以得出关系 ans[id] max(max(up[a], down[b]), dp_max[b] - dp_min[a])。 #include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;const int MAX_N (50000 5000);
const int MAX_M (MAX_N 2);
const int inf 0x3f3f3f3f;
int NE1, NE2, NE3, head1[MAX_N], head2[MAX_N], head3[MAX_N];void Init()
{NE1 NE2 NE3 0;memset(head1, -1, sizeof(head1));memset(head2, -1, sizeof(head2));memset(head3, -1, sizeof(head3));}int N, Q, ans[MAX_N], value[MAX_N], vis[MAX_N];struct Edge1 {int v, next;
} edge1[MAX_M];void Insert1(int u, int v)
{edge1[NE1].v v;edge1[NE1].next head1[u];head1[u] NE1;
}struct Edge {int v, id, next;
} edge2[MAX_M], edge3[MAX_M];void Insert2(int u, int v, int id, int flag)
{if (!flag) {edge2[NE2].v v;edge2[NE2].id id;edge2[NE2].next head2[u];head2[u] NE2;} else {edge3[NE3].v v;edge3[NE3].id id;edge3[NE3].next head3[u];head3[u] NE3;}
}int parent[MAX_N];
int up[MAX_N], down[MAX_N], dp_max[MAX_N], dp_min[MAX_N];int find(int x)
{if (x parent[x]) {return x;}int fa parent[x];parent[x] find(parent[x]);up[x] max(max(up[x], up[fa]), dp_max[fa] - dp_min[x]);down[x] max(max(down[x], down[fa]), dp_max[x] - dp_min[fa]);dp_max[x] max(dp_max[x], dp_max[fa]);dp_min[x] min(dp_min[x], dp_min[fa]);return parent[x];
}struct Node {int u, v;
} node[MAX_N];void Tarjan(int u)
{vis[u] 1;parent[u] u;//Q;for (int i head2[u]; ~i; i edge2[i].next) {int v edge2[i].v, id edge2[i].id;if (!vis[v]) continue;int fa find(v);Insert2(fa, v, id, 1);}for (int i head1[u]; ~i; i edge1[i].next) {int v edge1[i].v;if (vis[v]) continue;Tarjan(v);parent[v] u;}//edge3for (int i head3[u]; ~i; i edge3[i].next) {int id edge3[i].id;find(node[id].u);find(node[id].v);ans[id] max(max(up[node[id].u], down[node[id].v]), dp_max[node[id].v] - dp_min[node[id].u]);}
}int main()
{while (~scanf(%d, N)) {for (int i 1; i N; i) {scanf(%d, value[i]);up[i] down[i] 0;dp_max[i] dp_min[i] value[i];}Init();for (int i 1; i N; i) {int u, v;scanf(%d %d, u, v);Insert1(u, v);Insert1(v, u);}scanf(%d, Q);for (int i 1; i Q; i) {scanf(%d %d, node[i].u, node[i].v);Insert2(node[i].u, node[i].v, i, 0);Insert2(node[i].v, node[i].u, i, 0);}memset(vis, 0, sizeof(vis));Tarjan(1);for (int i 1; i Q; i) printf(%d\n, ans[i]);}return 0;
}转载于:https://www.cnblogs.com/wally/p/4477051.html
