<strong>题目描述 Description</strong>水果姐第二天心情也很不错，又来逛水果街。突然，cgh又出现了。cgh施展了魔法，水果街变成了树结构（店与店之间只有一条唯一的路径）。同样还是n家水果店，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。cgh给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去。求最多可以赚多少钱。水果姐向学过oi的你求助。输入描述 Input Description第一行n，表示有n家店下来n个正整数，表示每家店一个苹果的价格。下来n-1行，每行两个整数x，，y，表示第x家店和第y家店有一条边。下来一个整数m，表示下来有m个询问。下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。输出描述 Output Description有m行。每行对应一个询问，一个整数，表示面对cgh的每次询问，水果姐最多可以赚到多少钱。样例输入 Sample Input1016 5 1 15 15 1 8 9 9 151 21 32 42 52 66 74 81 91 1069 15 11 73 31 13 6样例输出 Sample Output71170015数据范围及提示 Data Size & Hint0<=苹果的价格<=10^80<n<=2000000<m<=10000
题解：因为没有修改，所以我们可以使用树上倍增来解决，
设fa[i][j]表示点i的第2^j个祖先
ma[i][j]表示点i到点fa[i][j]的最大值。
mi[i][j]表示点i到点fa[i][j]的最小值。
zma[i][j]表示点i到点fa[i][j]的最大获利。
fma[i][j]表示点fa[i][j]到点i的最大获利。
然后我们可以预处理出这四个数组。
即：
ma[x][i]=max(ma[fa[x][i-1]][i-1],ma[x][i-1]); mi[x][i]=min(mi[fa[x][i-1]][i-1],mi[x][i-1]); zma[x][i]=max(max(zma[fa[x][i-1]][i-1],zma[x][i-1]),ma[fa[x][i-1]][i-1]-mi[x][i-1]); fma[x][i]=max(max(fma[fa[x][i-1]][i-1],fma[x][i-1]),ma[x][i-1]-mi[fa[x][i-1]][i-1]);
然后我们求出询问的两个点的最近公共祖先，然后分别倍增，在走向最近公共祖先的路径上记录一下历史最小值，在远离最近公共祖先的路径上记录一下历史最大值（在途中和最大获利比较）。最后答案再和历史最大值-历史最小值比较一下即可。。。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,m,fa[1000001][15],w[1000001],point[1000001],next[1000001],u,v,cnt,deep[1000001],vis[1000001];int ma[1000001][15],mi[1000001][15],zma[1000001][15],fma[1000001][15];struct use{int st,en;}b[1000001];void add(int x,int y){++cnt;next[cnt]=point[x];point[x]=cnt;b[cnt].st=x;b[cnt].en=y;}void dfs(int x){vis[x]=1;for(int i=1;i<=14;i++){if(deep[x]<(1<<i))break;fa[x][i]=fa[fa[x][i-1]][i-1];ma[x][i]=max(ma[fa[x][i-1]][i-1],ma[x][i-1]);mi[x][i]=min(mi[fa[x][i-1]][i-1],mi[x][i-1]);zma[x][i]=max(max(zma[fa[x][i-1]][i-1],zma[x][i-1]),ma[fa[x][i-1]][i-1]-mi[x][i-1]);fma[x][i]=max(max(fma[fa[x][i-1]][i-1],fma[x][i-1]),ma[x][i-1]-mi[fa[x][i-1]][i-1]);}for(int i=point[x];i;i=next[i]){if(vis[b[i].en])continue;deep[b[i].en]=deep[x]+1;fa[b[i].en][0]=x;ma[b[i].en][0]=max(w[b[i].en],w[x]);mi[b[i].en][0]=min(w[b[i].en],w[x]);zma[b[i].en][0]=w[x]-w[b[i].en];fma[b[i].en][0]=w[b[i].en]-w[x];dfs(b[i].en);}}int lca(int x,int y){int t;if (deep[x]<deep[y]) swap(x,y);t=deep[x]-deep[y];for (int i=0;i<=14;i++)if (t&(1<<i)) x=fa[x][i];for (int i=14;i>=0;i–) if (fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}if (x==y)return x;elsereturn fa[x][0];}int main(){cin>>n;for (int i=1;i<=n;i++) scanf("%d",&w[i]);for (int i=1;i<=n-1;i++) {scanf("%d%d",&u,&v);add(u,v);add(v,u); }dfs(1);cin>>m;for (int i=1;i<=m;i++) {int maxx(-1000000),minn(1000000),t,x,y,ans(-100000); ans=0; scanf("%d%d",&x,&y);int z; z=lca(x,y);t=deep[x]-deep[z];if (t>0){for (int j=0;j<=14;j++){if (t&(1<<j)){ans=max(zma[x][j],ans);ans=max(ans,ma[x][j]-minn);minn=min(minn,mi[x][j]);x=fa[x][j];}}}t=deep[y]-deep[z]; if (t>0){for (int j=0;j<=14;j++){if (t&(1<<j)){ans=max(fma[y][j],ans);ans=max(ans,maxx-mi[y][j]);maxx=max(maxx,ma[y][j]);y=fa[y][j];}}}ans=max(maxx-minn,ans);printf("%d\n",ans); }}
一定要成为你工作最大的资产。
