【题解】[NOI2014] 购票 斜率优化 DP + 点分治 LuoguP2305 — Qiuly

考虑设 $dp_{u}$ 表示点 $u$ 的最少资金，有转移：
$$
\begin{aligned}
dp_u&=q_u+\min_{dis(u,v)\leq L_u} dp_v+(dep_u-dep_v)p_u\\
&=q_u+dep_up_u+\min_{dis(u,v)\leq L_u} dp_v-dep_vp_u\\
&=C_u+\min_{dis(u,v)\leq L_u} dp_v-dep_vp_u
\end{aligned}
$$
$v$ 是 $u$ 的祖先，时间复杂度 $O(n^2)$ 。

发现转移带的式子符合斜率优化，考虑如何斜率优化。

如果一个 $a$ 比 $b$ 更优：
$$
dp_a-dep_ap_u<dp_b-dep_bp_u\\
p_u<\frac{dp_b-dp_a}{dep_b-dep_a}
$$
然后由于 $p_u$ 不单调，需要每次二分查询。

---

很久很久很久很久没写斜率优化了正好来复习一波。

考虑 $y=kx+c$ ，意义就是令 $x=p_u$ 求 $y$ ，这么说来就是将前面的每个可以转移过来的点看做直线，然后每一次询问 $x=p_u$ 上的最小 $y$ 值。

考虑用李超树单调栈维护这些直线，由于 $x$ 不递增，每一次都需要二分查询。

（记住这是直线，忘记一切斜率优化的东西，直线就很自然了（

---

然后因为询问区间不等，对于序列上的做法，考虑 $\rm{CDQ}$ 分治：

• 求解左区间的 $dp$ 值。
• 将右区间的元素按照” 可以访问到左区间的最长后缀长度” 从小到大排序，排完后就是扫，然后左区间是从右到左加入直线。
• 递归右区间。

时间复杂度大概是 $O(n\log^2n)$ 的。

注意维护直线的细节。

对于树上的做法考虑点分治，对于当前重心：

• 先递归原树父亲。
• 然后在当前节点，计算上一个重心到原树父亲对点分治子树内” 不包括原树父亲的子树” 的贡献。
• 递归其他子树。

道理跟 $\rm{CDQ}$ 是一样的，需要注意的细节就是当前节点算第二部的时候到底要跳到哪里停止 … 不然复杂度就是假的，怕不是每次都给跳到根了。

将序列问题搬上树，可以用 $\rm{CDQ}$ 解决的问题一般也可以用点分治解决。
如果考虑点分治处理的路径问题会发现 $\rm{CDQ}$ 一样可以处理。
这两个东西本质可能差不多？

然后：

斜率优化维护直线需要根据查询点是否递增/直线斜率是否递增以及一系列问题来判断到底怎么维护直线。

注意你维护的是直线，别整没用的。

维护直线：

struct _ {
    int sta[N],top;
    struct Line {double k,c;} qwq[N];

    inline double slope(int x,int y) {
        return (qwq[x].c-qwq[y].c)/(qwq[y].k-qwq[x].k);
    }
    inline int query(double pos) {
        int l=2,r=top,ans=1;
        while(l<=r) slope(sta[mid-1],sta[mid])>=pos?ans=mid,l=mid+1:r=mid-1;
        return sta[ans];
    }
    inline void insert(int i) {
        qwq[i]=(Line){(double)-dep[i],(double)dp[i]};
        while(top>1&&slope(sta[top],i)>=slope(sta[top-1],sta[top])) qwq[sta[top--]]=(Line){0,0};
        sta[++top]=i;
    }
    inline void clear() {while(top) qwq[sta[top]]=(Line){0,0},sta[top--]=0;}
} qwq;

点分治：

inline void calc(int u,int pre) {
    top=0,pre=fa[pre],qwq.clear();
    for(int e=head[u];e;e=G[e].nxt) if(v!=fa[u]) get_dis(v,u,G[e].val);
    sta[++top]=mkp(L[u],u),std::sort(sta+1,sta+1+top);

    ll tmp=S[u];
    int now=fa[u];
    for(int t=1;t<=top;++t) {
        int i=sta[t].se;
        while(now!=pre&&tmp<=sta[t].fi) qwq.insert(now),tmp+=S[now],now=fa[now];
        int j=qwq.query(P[i]);
        if(j) chkmin(dp[i],Q[i]+dp[j]+(dep[i]-dep[j])*P[i]);
    }
}
void solve(int u,int pre) {
    vis[u]=true;
    if(fa[u]&&!vis[fa[u]]) rt=0,all=siz[fa[u]],get_rt(fa[u],0),solve(rt,pre);
    calc(u,pre);
    for(int e=head[u];e;e=G[e].nxt) if(!vis[v]) rt=0,all=siz[v],get_rt(v,0),solve(rt,u);
}