题解 P3994 【高速公路】

· · 题解

为什么题解都是请一色的二分还原啊...

总感觉有题解彼此潮汐的嫌疑

实际上并不需要什么二分

把朴素的dp转移写出来

发现是这样的：

dp_x=\min(dp_{u}+(dis_x-dis_u)*p_x+c_x)

设u,v均可以转移给k，且u<v

dp_u+(dis_k-dis_u)*p_k+c_k>dp_v+(dis_k-dis_v)*p_k+c_k dp_u-dis_u*p_k>dp_v-dis_v*p_k (dis_v-dis_u)*p_k>dp_v-dp_u p_k>\dfrac{dp_v-dp_u}{dis_v-dis_u}

不难发现我们要维护一个下凸壳

因为有p_{fa}\le p_u

所以沿途走下来我们可以O(n)的dp下来

但是跨越子树就做不到了...

仔细思考，我们发现我们对于这个单调队列只做了如下三种操作：

++head --tail q[tail]=x

所以，我们发现我们只是修改了head,tail和q[tail]而已...

所以就分别记录一下本次修改前的状态，然后还原回去即可...

如果按照出边对应点的点权排序，复杂度应该可以做到O(n\log n)

但我比较懒，所以没排，但还是过了...

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next ) 
#define drep( i, t, s ) for( register int i = t; i >= s; -- i )
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define LL long long
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int N = 1e6 + 5;
int n, num, L[N], q[N], fr, ed; 
int cnt, head[N], p[N], c[N] ;
LL dp[N], dis[N] ; 
struct E {
    int to, next, w ;
} e[N * 2];
void add( int x, int y, int z ) {
    e[++ cnt] = (E){ y, head[x], z }, head[x] = cnt ; 
}
double K( int x, int y ) {
    double yy = dp[x] - dp[y], xx = dis[x] - dis[y] ;
    return yy / xx ; 
}
inline void dfs( int x ) {
    int Hev = fr, Eev = ed ; 
    while( fr < ed && K( q[fr], q[fr + 1] ) < 1.0 * p[x] ) ++ fr ; 
    dp[x] = dp[q[fr]] + 1ll * p[x] * ( dis[x] - dis[q[fr]] ) + c[x] ; 
    while( fr < ed && K( q[ed], q[ed - 1] ) > K( q[ed], x ) ) -- ed ; 
    int ru = ++ ed, rm = q[ed] ; q[ed] = x ; 
    Next( i, x ) {
        dis[e[i].to] = dis[x] + e[i].w, dfs(e[i].to) ;
    }
    q[ru] = rm, fr = Hev, ed = Eev ; 
}
signed main()
{
    n = read() ; fr = 1 ; int x, y ; 
    rep( i, 2, n ) {
        x = read(), y = read(), add( x, i, y ), p[i] = read(), c[i] = read() ; 
    }
    dfs( 1 ) ;
    rep( i, 2, n ) printf("%lld\n", dp[i] ); 
    return 0;
}