本文共 2088 字，大约阅读时间需要 6 分钟。
题意：有n个城市，有n-1条边使各个城市相互直接或间接连通，给出一件货物在各城市的价格w[n]，然后给出q个询问，每个询问有两个城市s,t，问从s到t的路径上买入卖出货物盈利的最大值。注意：在某个城市买入，只能够在其后经过的城市卖出。
分析：假设询问从城市u到城市v的路径上所能获得的最大盈利值，又设lca为u,v的LCA，则u->v的路径就是u->lca->v，那么最大的盈利值就有可能出现在3种情况： 1.在u->lca中出现； 2.在lca->v中出现； 3.在u->lca->v中出现（即有跨过lca）。
第3种情况是比较容易解决的，我们只要求出lca->v中的最大值max_val，减去u->lca中的最小值min_val，max_val-min_val就是答案，因此对于这种情况我们可以设置ma[i][j]，mi[i][j]分别表示：
ma[i][j]：在i结点往上跳2j步到达的结点的路径当中的最大价格； mi[i][j]：在i结点往上跳2j步到达的结点的路径当中的最小价格。 对于第1,2种情况，我们同样可以考虑分治。以第1种情况为例，
设k为u->lca路径当中某个结点，那么u->lca可分解为u->k，k->lca。那么最终答案就同样会有3种情况： 1 .在u->k中出现； 2 .在k->lca中出现； 3 .在u->lca中出现（即跨过结点k）。 仿照第3种情况，我们同样
可以用倍增的思想来解决。设置up[i][j]表示： up[i][j]：在i结点往上跳2j步到达的结点的路径当中，最大的价格差（当然，最大价格出现的位置一定要在最小价格出现的位置之后）。 根据上述分析，不难推出up[i][j]的更新方式： up[i][j]=max(max(up[i][j-1],up[k][j-1]), ma[k][j]-mi[i][j]) 其中k=fa[i][j-1]，即在i结点往上跳2
j-1步到达的结点。
第2种情况与第3种情况相似，可以设置down[i][j]表示：
down[i][j]：设k为在i结点往上跳2j步到达的结点，down[i][j]为k->i的路径当中，最大的价格差。 代码如下：
#include #include #include #include #include #include using namespace std;typedef long long ll;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int depth[maxn],fa[maxn][20];ll ma[maxn][20],mi[maxn][20];ll up[maxn][20],down[maxn][20];ll w[maxn];bool vis[maxn];vector G[maxn];inline void read(ll &ret){ char c; while((c=getchar())&&(c>'9'||c<'0')); ret=0; while(c>='0'&&c<='9') ret=ret*10+c-'0', c=getchar();}inline void out(ll x){ if(x>9) out(x/10); putchar(x%10+'0');}void DFS(int u,int pre,int d){ fa[u][0]=pre; ma[u][0]=max(w[u],w[pre]); up[u][0]=max(0ll,w[pre]-w[u]); vis[u]=1; depth[u]=d; if(u!=1) mi[u][0]=min(w[u],w[pre]), down[u][0]=max(0ll,w[u]-w[pre]); else mi[u][0]=w[u], down[u][0]=0; for(int i=0;i lca中的最小值，同时也会发挥其他作用{ ll ans=0; for(int i=20;i>=0;--i) { if((1< v中的最大值，同样也会发挥其他作用{ ll ans=0; for(int i=20;i>=0;--i) { if((1< depth[u]) swap(u,v); int temp=depth[u]-depth[v]; for(int i=0;(1< <=temp;++i) { if((1< =0;--i) { if(fa[u][i]!=fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } } return fa[u][0];}int main(){ ll n; read(n); for(int i=1;i<=n;++i) read(w[i]); for(int i=1;i
PS：分治思想有时可以发挥很大的作用。
转载地址：http://vwdci.baihongyu.com/