POJ 3728 The merchant (LCA DP)

POJ - 3728

题目大意：给出一棵树，每次询问给出 $u,v$ 两点，在 $u$ 到 $v$ 的有向路径上先后选出两个点 $u^{\prime },v^{\prime }$ ，令 $w(v^{\prime })-w(u^{\prime })$ 最大。

可以想到三种情况：

1. 在 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)$ 的路径上买卖
2. 在 $\mathrm{l}\mathrm{c}\mathrm{a}(u,v)\to v$ 的路径上买卖
3. 在 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)$ 的路径上买入，在 $\mathrm{l}\mathrm{c}\mathrm{a}(u,v)\to v$ 的路径上卖出

第三种情况容易处理，可以暴力树剖 + 线段树求出两条路径上的最小权值和最大权值，然后求得答案。

但是第一种和第二种情况不好处理，问题在于选出的 $u^{\prime },v^{\prime }$ 有先后顺序。

这里给出倍增求 LCA + DP 的方法。

在倍增求 LCA 的时候，我们可以顺带求出一些值，方便我们后面计算答案。

设 $\mathrm{f}\mathrm{a}(u,i)$ 表示 $u$ 的 $2^i$ 级祖先，那么我们可以求出 $u$ 到 $\mathrm{f}\mathrm{a}(u,i)$ 的一下参数：

1. $f_{\mathrm{u}\mathrm{p}}(u,i)$ 表示 $u\to \mathrm{f}\mathrm{a}(u,i)$ 上的最大收益
2. $f_{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}(u,i)$ 表示 $\mathrm{f}\mathrm{a}(u,i)\to u$ 上的最大收益
3. $f_{\max }(u,i)$ 表示 $u$ 和 $\mathrm{f}\mathrm{a}(u,i)$ 之间的最大权值
4. $f_{\min }(u,i)$ 表示 $u$ 和 $\mathrm{f}\mathrm{a}(u,i)$ 之间的最小权值

对于参数 3 , 4 ，我们可以这样求：
fmax⁡(u,i)=max⁡{fmax⁡(u,i−1),fmax⁡(fa(u,i−1),i−1)}fmin⁡(u,i)=min⁡{fmin⁡(u,i−1),fmin⁡(fa(u,i−1),i−1)}\begin{aligned} f_{\max}(u,i)&=\max\{f_{\max}( u,i-1),f_{\max}({\rm fa}(u,i-1),i-1)\}\\[2ex] f_{\min}(u,i)&=\min\{f_{\min}(u,i-1),f_{\min}({\rm fa}(u,i-1),i-1)\} \end{aligned} fmax​(u,i)fmin​(u,i)​=max{fmax​(u,i−1),fmax​(fa(u,i−1),i−1)}=min{fmin​(u,i−1),fmin​(fa(u,i−1),i−1)}​
因为在求 $\mathrm{f}\mathrm{a}(u,i)$ 的时候，$\mathrm{f}\mathrm{a}(u,i)=\mathrm{f}\mathrm{a}(\mathrm{f}\mathrm{a}(i-1),i-1)$ ，所以 $u$ 和 $\mathrm{f}\mathrm{a}(u,i-1)$ 之间的最值与 $\mathrm{f}\mathrm{a}(u,i-1)$ 和 $\mathrm{f}\mathrm{a}(u,i)$ 之间的最值对 $u$ 和 $\mathrm{f}\mathrm{a}(u,i)$ 之间的最值有贡献。

同理，我们可以得出参数 1 , 2 的方程，只不过要注意，除了 $u$ 和 $\mathrm{f}\mathrm{a}(u,i-1)$ 之间的贡献与 $\mathrm{f}\mathrm{a}(u,i-1)$ 和 $\mathrm{f}\mathrm{a}(u,i)$ 之间的贡献，还要考虑直接跨过 $\mathrm{f}\mathrm{a}(u,i-1)$ 整段区间的最值 $f_{\max }-f_{\min }$
fup(u,i)=max⁡{fup(u,i−1),fup(fa(u,i−1),i−1),fmax⁡(fa(u,i−1),i−1)−fmin⁡(u,i−1)}fdown(u,i)=max⁡{fdown(u,i−1),fdown(fa(u,i−1),i−1),fmax⁡(u,i−1)−fmin⁡(fa(u,i−1),i−1)}\begin{aligned} f_{\rm up}(u,i) &= \max\{f_{\rm up}(u,i-1),f_{\rm up}({\rm fa}(u,i-1),i-1),f_{\max}({\rm fa}(u,i-1),i-1)-f_{\min}(u,i-1)\}\\[2ex] f_{\rm down}(u,i) &= \max\{f_{\rm down}(u,i-1),f_{\rm down}({\rm fa}(u,i-1),i-1),f_{\max}(u,i-1)-f_{\min}({\rm fa}(u,i-1),i-1)\} \end{aligned} fup​(u,i)fdown​(u,i)​=max{fup​(u,i−1),fup​(fa(u,i−1),i−1),fmax​(fa(u,i−1),i−1)−fmin​(u,i−1)}=max{fdown​(u,i−1),fdown​(fa(u,i−1),i−1),fmax​(u,i−1)−fmin​(fa(u,i−1),i−1)}​

但是这仅仅是预处理部分，处理这些参数有助于我们待会儿 DP.

一次询问给出 $u,v$ ，那么自然要求其 LCA ，上面我们已经预处理了一些信息，然后考虑利用这些信息在倍增求 LCA 的过程中计算答案。

处理 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)$ 的过程：

在向上跳的过程中，要求最大收益，那么每一次向上跳都可以得知其中一段的最大权值，于是我们只要记录一个当前最小权值，然后在跳的时候更新一下答案，之后再更新这个最小权值，如此反复就可以求得 $u\to \mathrm{l}\mathrm{c}\mathrm{a}$ 过程中的最大收益。

在跳的过程中，保持更新
ans=max⁡{fmax⁡(u,i)−m,ans}m=min⁡{fmin⁡(u,i),m}{\rm ans} = \max\{f_{\max}(u,i)-m,{\rm ans}\}\\ m = \min\{f_{\min}(u,i),m\} ans=max{fmax​(u,i)−m,ans}m=min{fmin​(u,i),m}
同理，处理 $\mathrm{l}\mathrm{c}\mathrm{a}(u,v)\to v$ 的过程也是类似的
ans=max⁡{mx−fmin⁡(u,i),ans}mx=max⁡{fmax⁡(u,i),mx}{\rm ans} = \max\{mx-f_{\min}(u,i),{\rm ans}\}\\ mx = \max\{f_{\max}(u,i),mx\} ans=max{mx−fmin​(u,i),ans}mx=max{fmax​(u,i),mx}
最后跳到 $\mathrm{l}\mathrm{c}\mathrm{a}(u,v)$ 的时候，我们会发现先前记录的 $m$ 和 $mx$ 恰好就是结点到 LCA 链上的最小值和最大值，于是再更新一次答案 ans=max⁡{ans,mx−m}{\rm ans} = \max\{{\rm ans},mx-m\}ans=max{ans,mx−m} 就计算出答案了。

预处理时间复杂度 $O(N)$ ，回答询问的时间复杂度 $O(Q\log N)$

启示：DP 可以加载到倍增求 LCA 上，用于减小时间复杂度。树上的最值问题要考虑运用 DP.

void dfs(int u,int pre)
{dep[u] = dep[pre] + 1;for(int i = 1;i <= 25;i ++){fa[u][i] = fa[fa[u][i - 1]][i - 1];maxf[u][i] = max(maxf[fa[u][i - 1]][i - 1],max(w[u],maxf[u][i - 1]));//从 u 到 fa(u,i) 路径上最大权值 minf[u][i] = min(minf[fa[u][i - 1]][i - 1],min(w[u],minf[u][i - 1]));//从 u 到 fa(u,i) 路径上最小权值 upf[u][i] = max(max(upf[fa[u][i - 1]][i - 1],upf[u][i - 1]),maxf[fa[u][i - 1]][i - 1] - minf[u][i - 1]);//从 u 向上先买入后卖出的最大收益 downf[u][i] = max(max(downf[fa[u][i - 1]][i - 1],downf[u][i - 1]),maxf[u][i - 1] - minf[fa[u][i - 1]][i - 1]);//从 fa(u,i) 向下先买入后卖出的最大收益 }for(int i = head[u],v = 0;i;i = e[i].nxt){v = e[i].to;if(v == pre) continue;fa[v][0] = u;maxf[v][0] = max(w[u],w[v]);minf[v][0] = min(w[u],w[v]);upf[v][0] = max(0,w[u] - w[v]);downf[v][0] = max(0,w[v] - w[u]);dfs(v,u);}return ;
}int solve(int u,int v)
{int tmpx = u;int tmpy = v;int res = 0;int maxup = w[v];int mindown = w[u];if(dep[tmpx] < dep[tmpy]){for(int i = 25;i >= 0;i --){if(dep[fa[tmpy][i]] >= dep[tmpx]){res = max(res,maxup - minf[tmpy][i]);maxup = max(maxup,maxf[tmpy][i]);res = max(res,downf[tmpy][i]);//tmpy = fa[tmpy][i];}}}else{for(int i = 25;i >= 0;i --){if(dep[fa[tmpx][i]] >= dep[tmpy]){res = max(res,maxf[tmpx][i] - mindown);mindown = min(mindown,minf[tmpx][i]);res = max(res,upf[tmpx][i]);//tmpx = fa[tmpx][i];}}}if(tmpx == tmpy) return res;for(int i = 25;i >= 0;i --){if(fa[tmpx][i] != fa[tmpy][i]){res = max(res,maxf[tmpx][i] - mindown);res = max(res,maxup - minf[tmpy][i]);maxup = max(maxup,maxf[tmpy][i]);mindown = min(mindown,minf[tmpx][i]);res = max(res,max(upf[tmpx][i],downf[tmpy][i]));tmpx = fa[tmpx][i];tmpy = fa[tmpy][i];}}res = max(res,maxf[tmpx][0] - mindown);res = max(res,maxup - minf[tmpy][0]);maxup = max(maxup,maxf[tmpy][0]);mindown = min(mindown,minf[tmpx][0]);res = max(res,maxup - mindown);return res;
}