自动搬运

查看原文

来自洛谷，原作者为

	pkh68 Friendship is magic!

搬运于2025-08-24 21:55:20，当前版本为作者最后更新于2018-10-05 20:57:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题面描述

给定一颗树，在树上做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)}$$

考虑下图：

$j2$肯定不是最优转移，所以最优转移为下凸包。

又因为$Pi$单调递增，所以用单调队列维护即可。

但是，此题是在树的链上转移，所以$dfs$时一颗子树的决策会影响另一颗子树的凸包，而这不符合题意。

我们仔细观察单调队列的性质：发现每次修改只是$++h$,而队列元素本身没有变化，至于队尾，每次是$--t$,并且只修改一个元素。

我们便有了一个自然的思路：记下每一个节点对应的$h$，$t$和对应的被修改的元素，每一次回溯时还原。

但这样一个节点会入队出队多次，复杂度上界仍为$O(n^2)$。

我们考虑二分查找每一次更新的$h$，$t$，这样对于每一个节点有两次二分查找， 回溯还原、状态转移复杂度皆为$Q(1)$，所以总复杂度为$O(nlogn)$。

代码如下

#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$，而是用二分查找降低了复杂度（因为每一次只修改了一个元素），要仔细体会。