【ロゴウP 3994】高速道路

タイトルリンク
タイトルの説明
C国は四通八達の高速道路網樹を持ち、そのうちn都市があり、都市間は全部でn-1本の高速道路で接続されている.首都1号都市を除いて、各都市に地元の旅客輸送会社があり、全国各地に発車して行くことができ、いくつかの高速道路が他の都市につながっている.これは木型構造で、1号都市(首都)が根付いている.i番都市から車でj番都市に行く人がいるとしたら、Pi*(i都市からj都市までの距離)+Qi元かかります.首都から遠くなるほど、国の規制が緩むため、首都から遠くなるほど、旅客会社のPi(単位距離価格)が大きくなり、高速道路網を首都を根幹とする有根樹と見なせば、i号都市はj号都市のある祖先であり、Pi<=Pjが存在するに違いない.
Sol
祖先からの移転だけを考えているふりをします
次のようになります.
f[ i ]=min{f[ j ]−P[ i ]∗Dis[ j ]}+Q[ i ]+P[ i ]∗Dis[ i ] f [   i   ] = m i n { f [   j   ] − P [   i   ] ∗ D i s [   j   ] } + Q [   i   ] + P [   i   ] ∗ D i s [   i   ]
中は裸の傾きが最適化されていますが、明らかに直接やってはいけません.これは木だからです.
スロープ最適化をより深く理解する必要があります
1つの暴力的な方法は、単調なキューの配列を維持するために、持続可能なセグメントツリーを使用することです.
しかし、1つの要素を考慮するたびに、最初のポインタを変更し、複数のキューの要素(現在の要素で覆われている)を変更するだけで、直接暴力的に操作を取り消すことができ、満点を得ることができます.
しかし、実はこのように複雑さをするのは間違っています.そうすれば、1つの要素が1回入隊しただけでなく、繰り返し追加される可能性があります.そうすれば、カードが落ちます.
スロープ最適化の本質は凸包を維持することであるため、すなわち中の直線のスロープは単調であるため、暴力的にペアを出すことなく、二分という位置に変えて一度にチームを出ることができ、複雑度は安定したO(nlogn)O(n l o g n)になる.
(でも直接过ごすのは何か悪いことがあります)
暴力が出る:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();int t=1;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-' )t=-1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
    return x*t;
}
const int N=1e6+10;
struct edge{
    int to,next;
}a[N];
int cur[N];int cnt=0;
inline void add(int x,int y){a[++cnt]=(edge){y,cur[x]};cur[x]=cnt;}
typedef long long ll;
int P[N];
int Q[N];
int fa[N],W[N];
int n;
int que[N];int h,t;
ll dp[N],dis[N];
int head[N],tail[N],pos[N],pre[N];
typedef double db;
inline db getk(int p,int q){
    return (db)(dp[p]-dp[q])/(db)(dis[p]-dis[q]);
}
void dfs(int u)
{
    head[u]=h;tail[u]=t;
    while(h1])<=1.00*P[u]) ++h;
    dp[u]=dp[que[h]]+(dis[u]-dis[que[h]])*P[u]+Q[u];
    while(h1])>getk(u,que[t])) --t;
    pre[u]=que[++t];que[t]=u;pos[u]=t;
    for(register int v,i=cur[u];i;i=a[i].next){
        v=a[i].to;dis[v]=dis[u]+W[v];dfs(v);
    }
    h=head[u];t=tail[u];que[pos[u]]=pre[u];
    return;
}
int main()
{
    n=read();
    for(register int i=2;i<=n;++i) fa[i]=read(),W[i]=read(),P[i]=read(),Q[i]=read(),add(fa[i],i);
    h=1;t=0;
    dfs(1);
    for(register int i=2;i<=n;++i) printf("%lld
",dp[i]);
    return 0;
}