_WA自动机的blog

过期高中生。

[luogu P3994]高速公路

发表于 更新于 阅读次数： Valine：

斜率优化dp

题目背景

C国拥有一张四通八达的高速公路网树，其中有n个城市，城市之间由一共n-1条高速公路连接。除了首都1号城市，每个城市都有一家本地的客运公司，可以发车前往全国各地，有若干条高速公路连向其他城市，这是一个树型结构，1号城市（首都）为根。假设有一个人要从i号城市坐车出发前往j号城市，那么他要花费Pi*（i城市到j城市的距离）+Qi元。由于距离首都越远，国家的监管就越松，所以距离首都越远，客运公司的Pi（单位距离价格）越大，形式化的说，如果把高速路网看成一棵以首都为根的有根树，i号城市是j号城市的某个祖先，那么一定存在Pi<=Pj。

题目描述

大宁成为了国家统计局的调查人员，他需要对现在的高速路网进行一次调查，了解从其他每一个城市到达首都1号城市所花费的金钱(路径必须是简单路径)。

因为有非常多转车（或不转车）的抵达首都的方法，所以人工计算这个结果是十分复杂的。大宁非常的懒，所以请你编写一个程序解决它。 # 题解
这道题的dp方程比较显然： \[f[u]=min_{lca(u,v)=v}\{f[v]+P[u]*(depth[u]-depth[v])+Q[u]\}\] 直接dp是\(O(n^2)\)的。有关于uv的乘积项，depth单调，考虑斜率优化。
整理得： \[f[u]=min_{lca(u,v)=v}(-depth[v]*P[u]+f[v])+Q[u]+depth[u]*P[u])\] 则以\(-depth[v]\)为斜率，\(P[u]\)为横坐标，\(f[v]\)为截距，化为一个标准的斜率优化柿子。

我们发现x坐标是不单调的，这意味着我们需要维护整个凸包（单调栈），然后二分找最优的决策点。这也是老套路了。

但是重点并不在于此：这是树上的dp，我们不能像维护序列一样直接令决策点入队出队，因为这样的话每个点不一定只被入队一次，最坏情况仍然是\(O(n^2)\)。那我们怎么办呢？

用主席树实现可持久化栈

点分治优化dp

上面的做法不太好写而且常数巨大...我们有更为优雅的方法：

考虑到斜率单调，那么新来的直线排除掉的旧决策一定是栈顶连续的一段区间。由于决策的单调性，我们可以通过二分找到应该插入新决策的位置(这里找决策点的方法其实和单调队列相同，只是把暴力出队改成二分找合法位置罢了），并让决策入栈。我们发现这样的话其实只是改变了栈顶的位置并修改了一个元素，所以我们在回溯的时候把栈顶和修改的元素改回去，就实现了\(O(n\lg n)\)的优秀做法...
不过因为数据太水被暴力踩爆了

下面是喜闻乐见的代码~（求评价码风qwq） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>

const int maxn=1e6+100;

struct Edge
{
    int to,next,w;
}edge[maxn<<1];

int head[maxn],cnt;
int stack[maxn],P[maxn],Q[maxn],fa[maxn];
int64_t f[maxn],depth[maxn];

inline void add(int u,int v,int w)
{
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}

template<class T>inline T max(T a,T b){return a<b?b:a;}
template<class T>inline T min(T a,T b){return a<b?a:b;}

inline int64_t K(int x){return -depth[x];}
inline int64_t B(int x){return f[x];}
inline int64_t C(int x){return Q[x]+(int64_t)depth[x]*P[x];}
inline double intersection(int x,int y){return ((double)B(x)-B(y))/(K(y)-K(x));}

//f[u]=min_{lca(u,v)=v}(-depth[v]*P[u]+f[v])+Q[u]+depth[u]*P[u])

inline int findbest(int x,int top)
{
    int l=1,r=top;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (intersection(stack[mid-1],stack[mid])<=P[x]) l=mid+1;
        else r=mid-1;
    }
    return stack[r];//蒟蒻这里写成了return r WA到怀疑人生..
}

inline int findpos(int x,int top)
{
    int l=1,r=top;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (intersection(stack[mid-1],x)>intersection(stack[mid],stack[mid-1])) l=mid+1;
        else r=mid-1;
    }
    return r;
}

inline int64_t calc(int x,int top)
{
    int dec=findbest(x,top);
    return K(dec)*P[x]+B(dec)+C(x);
}

inline void dfs(int u,int top,int ff)
{
    f[u]=calc(u,top);
    top=findpos(u,top)+1;
    int pre=stack[top];
    stack[top]=u;
    for (int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        depth[v]=depth[u]+edge[i].w;
        if (v==ff) continue;
        dfs(v,top,u);
    }
    stack[top]=pre;
}

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=2,w;i<=n;++i)
        scanf("%d%d%d%d",fa+i,&w,P+i,Q+i),add(fa[i],i,w);
    for (int i=head[1];i;i=edge[i].next)
    {
        int v=edge[i].to;
        depth[v]=edge[i].w;
        dfs(v,0,1);
    }
    for (int i=2;i<=n;++i)
        printf("%lld\n",f[i]);
}