题解 P3994 【高速公路】
pkh68
·
·
题解
题面描述
给定一颗树，在树上做dp。
解析
这道题转移还是比较好想的，朴素的方程如下：
f(i)=min(f(j)+(deep(i)-deep(j))*Pi+Qi)(j∈Prei)
但这样的复杂度是O(n^2)的，过不掉1000000的数据。
所以我们考虑斜率优化：设决策j比决策k优秀（j<k）。
那么就有：
f(j)+(deep(i)-deep(j))*Pi+Qi<f(k)+(deep(i)-deep(k))*Pi+Qi
即：
f(j)-deep(j)*Pi<f(k)-deep(k)*Pi
Pi<\frac{f(k)-f(j)}{deep(k)-deep(j)}
考虑下图：
又因为$Pi$单调递增，所以用单调队列维护即可。
但是，此题是在树的链上转移，所以$dfs$时一颗子树的决策会影响另一颗子树的凸包，而这不符合题意。
我们仔细观察单调队列的性质：发现每次修改只是$++h$,而队列元素本身没有变化，至于队尾，每次是$--t$,并且只修改一个元素。
我们便有了一个自然的思路：记下每一个节点对应的$h$，$t$和对应的被修改的元素，每一次回溯时还原。
但这样一个节点会入队出队多次，复杂度上界仍为$O(n^2)$。
我们考虑二分查找每一次更新的$h$，$t$，这样对于每一个节点有两次二分查找，
回溯还原、状态转移复杂度皆为$Q(1)$，所以总复杂度为$O(nlogn)$。
### 代码如下
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define re register
#define N 1000005
#define LL long long
using namespace std;
int n,h,t,Etot=0,head[N],p[N],q[N];
LL deep[N],f[N];
struct Edge{ int to,next,dis; }edge[N];
inline void add(int u,int v,int dis){ edge[++Etot]=(Edge){v,head[u],dis};head[u]=Etot; }
inline double slope(int j,int k){ return 1.0*(f[k]-f[j])/(deep[k]-deep[j]); }
void dfs(int u,int depth){
deep[u]=depth;
for(re int i=head[u];i;i=edge[i].next) dfs(edge[i].to,depth+edge[i].dis);
}
void dp(int u){
int now_h=h,now_t=t,l,r,mid,tmp;
l=h;r=t-1;tmp=-1;
while(l<=r){
mid=(l+r)>>1;
if(1.0*p[u]<=slope(q[mid],q[mid+1])) tmp=mid,r=mid-1;
else l=mid+1;
}
if(tmp!=-1) h=tmp;else h=t;
f[u]=f[q[h]]+(deep[u]-deep[q[h]])*p[u]+q[u];
l=h;r=t-1;tmp=-1;
while(l<=r){
mid=(l+r)>>1;
if(slope(q[mid],q[mid+1])<slope(q[mid+1],u)) tmp=mid,l=mid+1;
else r=mid-1;
}
if(tmp!=-1) t=tmp+1;else t=h;
int now_q=q[++t];q[t]=u;
for(re int i=head[u];i;i=edge[i].next) dp(edge[i].to);
h=now_h;q[t]=now_q;t=now_t;
}
int main(){
scanf("%d",&n);
for(re int i=2,u,w;i<=n;++i){
scanf("%d%d%d%d",&u,&w,&p[i],&q[i]);
add(u,i,w);
}
dfs(1,0);
for(re int i=head[1];i;i=edge[i].next) h=t=1,q[h]=1,dp(edge[i].to);
for(re int i=2;i<=n;++i) printf("%lld\n",f[i]);
return 0;
}
```
### 后记
这道题思路非常巧妙，在$dfs$时没有按套路更改$h$，$t$，而是用二分查找降低了复杂度（因为每一次只修改了一个元素），要仔细体会。