在今天的考试中，我们遇到了一道极其恶心的题。看似是斜率优化的树形 Dp，实际暗藏玄机。

harbingers

题意：给定一棵树，除１号以外的每个节点上都有一个快递小哥。每个节点都可能有快递要送到一号节点去，而快递也总是沿最短路运输。快递每经过一个节点，可以选择：继续由当前的快递小哥运输，或更换这个节点的快递小哥运输。每个快递小哥有２个参数，分别为 Si,Ti 表示接到快递出发前的准备时间，和通过单位距离的时间。现在给出 n(n<=100000) 个节点和 n-1 条给定长度的路，求每个节点的快递运送到１号节点的最短时间。

---

分析：

数形结合－数

首先，由于快递总是沿着一条链运输，我们不妨先对链的情况进行分析。
对于一条链，我们设１号节点为目标节点，f[i] 表示第 i 个节点运到１号节点的最短时间。那么有：
$$
f[i]=min(f[j]+dist(j,i)T[i]+S[i])
$$
对于当前的 i, 我们设 a<b, 且 j 取 a 时比 b 时更优。
那么显然有：
$$
f[a]+dist(a,i)T[i]+S[i]<f[b]+dist(b,i)T[i]+S[i]
$$

推出：
$$
\frac{f[a]-f[b]}{dist(b,i)-dist(a,i)}<T[i]
$$
不妨设 d[i] 表示 i 号节点到 1 号节点的距离。那么有：
$$
\frac{f[a]-f[b]}{d[a]-d[b]}>T[i]
$$
很显然，如果上面的式子成立，那么 a 比 b 优，反之 b 比 a 优。
又因为上面的式子很美妙，我们可以以 d[i] 为横轴，f[i] 为总轴花出图，理解一下。我们会收获以下几点感悟：
1. 如果当前的点越靠近横轴远离总轴，这个点会比较优，反之。
2. 这个函数的转移不满足决策单调性，因为如果有一个快递小哥跑地特别快，他会直接跑到根节点，不需要转移。
由于以上的两点，再结合公式，我们会发现寻找决策点 (即最优的 j) 的方法：
我们在空间里画上所有已知的点 (d[i],f[i])，现在对于 d 大于它们的新的点 A，我们画直线 y=T[A]x+b;
它的 b 从负无穷开始逐渐增大，过程中遇到的第一个点就是对于 A 的最佳转移。为什么呢？因为这个点左边的点与它连线的斜率小于 T[A]，可知它比左边的点优，同理它比右边的点优。
这样， 我们理解了我们要做什么，要如何利用空间中的点理解这道题，我们就可以抛开数字和公式，来看图形化的解法。

---

数形结合－形

通过刚才的分析，我们知道了我们需要维护一个点集，并且对于任意一条斜率的直线我们需要知道它会最先碰到哪个点。这其实就是一个凸包。
这个凸包要有如下操作：
1. 在最右端插入一个新的点。
2. 查询某个斜率的直线向上平移最先遇到哪个点。
这两个操作十分容易做到，而且都可以在 logn 时间内完成。对于操作１，我们二分找到这个点和哪个点的连线会构成凸包的一部分，删除那个点后面的点即可。对于操作二，我们二分找到凸包上哪个点与左右相邻的点的连线的斜率分别比给定的斜率小和大。(需要意会)


这样我们就解决了链的问题。这时候我们只需要将链推广到树的问题。

---

链->树

在树上 Dp 时，我们处理的链会在尾端追加和删除。
那么是不是我们只要不断改变链的尾端，同时维护凸包就可以了呢？
不！
由于每从父节点转移到子节点，我们会将凸包最右边的某些点删除再添加新的点，而删除后的点我们暂时没有好的办法添加回去，从而会影响到以后的转移。这种方法固然不可取。
解决办法１：我们用栈来维护凸包，从父节点转移到子节点时，我们在每次删除节点时保存删除的节点，从子节点回溯到父节点时把删除的点补回去。这样最然可行，但由于每个点可能有多个子节点，所以它之前的点可能会被删除添加多次，时间复杂度达到 $O(N^2logN)$
解决办法２：还是用栈来维护凸包，从父节点转移到子节点时，删除节点后数据仍然留在栈里，只是更新栈顶位置，同时记录旧的栈顶位置。此时再 push 新的点，同时记录被这个新的点覆盖的点是什么。回溯时只需要还原被覆盖的点，同时还原旧的栈顶位置，这时候的栈就和以前一模一样了。总复杂度只有 $O(NlogN)$
我们就顺利解决了这个问题。

---

启示

大多数斜率优化的题目是有决策单调性的，并且插入的新决策总是在旧决策的后面。
但是如果不是这样呢？
1. 没有决策单调性，新决策插入在旧决策后面 (即按顺序插入的点 x 坐标递增)：
就比如这到题，我们依旧可以用线性结构 (栈、队列) 维护一个凸包，选择最优决策可以二分查找。
同样的，我们如果使用 Splay 等数据结构维护凸包同样是可行的，但是遇到这道题的 undo 操作就不太好用了。
2. 没有决策单调性，新决策不一定插入在旧决策后面 (x 坐标不递增)：
这样我们只能用 Splay 等数据结构维护。Splay 按 x 坐标排列，同时每插入一个点尝试着删除它左右的不构成凸包的点。

---

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define MX 300005

using namespace std;

typedef long long ll;

int fst[MX],nxt[MX],v[MX];
ll d[MX],lnum=-1;
ll wt[MX],mt[MX];   //time to waite / time to move
int n;

void addeg(int nu,int nv,int nw)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
    d[lnum]=nw;
}

void input()
{
    memset(fst,0xff,sizeof(fst));
    int a,b,c;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addeg(a,b,c);
        addeg(b,a,c);
    }
    for(int i=2;i<=n;i++)scanf("%lld%lld",&wt[i],&mt[i]);
}

ll dep[MX];
ll f[MX];
int q[MX],h;

inline double slope(int l,int r)
{
    return (double)(f[r]-f[l])/(double)(dep[r]-dep[l]);
}

inline int sfind(int l,int r,double slp)
{
    int mid=0;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(slope(q[mid-1],q[mid])>slp)r=mid-1;
        else if(slope(q[mid],q[mid+1])<slp)l=mid+1;
        else return mid;
    }
    return mid;
}

inline int tfind(int r,int x)
{
    int l=1,mid=0;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(slope(q[mid],q[mid+1])<slope(q[mid],x))l=mid+1;
        else if(slope(q[mid-1],q[mid])>slope(q[mid],x))r=mid-1;
        else return mid;
    }
    return mid;
}

int opt=0;

void dp(int x,int fa,ll dd)
{
    int lh,pre;
    dep[x]=dd;
    int blg;
    blg=sfind(1,h,mt[x]);
    f[x]=f[q[blg]]+(dep[x]-dep[q[blg]])*mt[x]+wt[x];
    lh=h;
    h=tfind(h,x);
    pre=q[++h];
    q[h]=x;
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(v[i]==fa)continue;
        dp(v[i],x,dd+d[i]);
    }
    q[h]=pre;
    h=lh;
}

void work()
{
    dp(1,0,1);
    for(int i=2;i<=n;i++)printf("%lld ",f[i]);puts("");
}

int main()
{
    freopen("harbingers.in","r",stdin);
    freopen("harbingers.out","w",stdout);
    input();
    work();
    return 0;
}