不错的一道码农题。

首先是个dp很显然了。

然后展开发现是个斜率优化不错。

但是取值有范围的。。。。

直接单调队列并不可以，因为凸包这个东西不是独立贡献答案的。

方法比较多，，

 

法一：

直观的想法是，既然可以转移的是一个区间，那么我们能不能快速得到这个区间的凸包呢？

线段树维护凸包应运而生。

只要在所有拆出来的区间中，分别在其维护的凸包上二分斜率即可。所有的值取min

但是如果dfs顺序来做的话，必须要支持凸包的撤销操作，，，，但是凸包的复杂度是均摊O(1)的，，，可以被特殊构造卡到O(n)。。。。

所以考虑能不能避免撤销操作。

还有没有什么可以动态处理树链的方法呢？

似乎只有树链剖分了。这样用dfn序维护整颗树即可。

 

修改：

如果处理好一个点的答案，

dfs询问处理的时候，也按照dfn序处理，这样就是不断在线段树最后加入一个点了。

凸包怎么办？可以暴力修改线段树一个链上的凸包，但是要对dis二分，而且常数极大。。

考虑到，每次询问都是一个之前dfn的区间，所以，当处理了1~3的dfn序之后，代表1~4的区间一定不用来询问。

所以，当一个区间的最后一个点加入之后，暴力把两个儿子合并即可。这样总线段树凸包的总复杂度O(nlogn)

询问：

树链剖分跳重链，把重链上有关的区间内的凸包上二分一下。注意lv[x]的边界处理。我是在树链剖分的时候额外二分了一下（其实线段树再记录min，max也可以）

O(nlog^3n)其中，树剖的logn不满，二分的logn更虚，所以实际跑的不错。

#include
      
       #define il inline#define reg register int#define numb (ch^'0')#define int long long#define mid ((l+r)>>1)#define ls (x<<1)#define rs (x<<1|1)#define fi first#define se secondusing namespace std;typedef long long ll;il void rd(ll &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=2e5+5;const ll inf=0x3f3f3f3f3f3f3f3f;int n,m;int dfn[N],df,fdfn[N],sz[N];int dep[N];int fa[N];ll dis[N];struct edge{    int nxt,to;    ll val;}e[2*N];int hd[N],cnt;ll pv[N],qv[N],lv[N];int top[N],son[N];void add(int x,int y,ll z){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].val=z;    hd[x]=cnt;}ll ans[N];void dfs1(int x,int d){    sz[x]=1;    dep[x]=d;    for(reg i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        dis[y]=dis[x]+e[i].val;        dfs1(y,d+1);        sz[x]+=sz[y];        if(sz[y]>sz[son[x]]) son[x]=y;    }}void dfs2(int x){    dfn[x]=++df;fdfn[df]=x;    if(!top[x]) top[x]=x;    if(son[x]) top[son[x]]=top[x],dfs2(son[x]);    for(reg i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(y==son[x]) continue;        dfs2(y);    }}struct node{    vector
       
        
          >tu;    ll mi;//mindis }t[4*N];int b[N],tot;double cross(ll x1,ll y1,ll x2,ll y2){    return (double)x1*y2-(double)x2*y1;}void pop(int x,ll d,ll f){    while(t[x].tu.size()>1){        int size=t[x].tu.size();    //    cout<<" size "<
         
          =0) t[x].tu.pop_back();        else break;    }    t[x].tu.push_back(make_pair(d,f));}void pushup(int x){//    cout<<" pushing "<
          
           <
           
            y2) return inf; return -inf; } return ((double)y1-(double)y2)/((double)x1-(double)x2);}ll query(int x,int l,int r,int L,int R,ll k){ //dis>=c // return f[j]-dis[j]*k if(L<=l&&r<=R){ ll ret=0;// if(t[x].mi>=c){// // }else{// ret=query(x<<1,l,mid,L,R,c,k);// ret=min(ret,query(x<<1|1,))// } int le=0,ri=t[x].tu.size()-1; while(le<=ri){ int md=(le+ri)>>1; if(md==0){ if(le==ri) ret=0; else{ ll t0=t[x].tu[0].se-t[x].tu[0].fi*k; ll t1=t[x].tu[1].se-t[x].tu[1].fi*k; if(t0
            
             lv[x]) break; if(!y) break; if(dis[x]-dis[top[y]]<=lv[x]){ //cout<<" goto top "<
            
           
          
         
        
       
      

 

 

法二：

这个跳树链实在还是多一个logn比较吃亏

如果可以dfs顺序来做就好了。这样直接一条链下来，凸包上直接二分就好。

上面已经分析，这样不能撤销。

树上求链还有什么算法呢？

点分治！

我们找到当前的重心H，先把H和根相连的部分和根的其他子树递归下去。

，，把和根相连的部分的这条链找出来，建一个凸包。

H的所有儿子的值也许都可以在这个凸包上找到决策点，dfs这些儿子的子树然后在凸包上二分

递归H的子树部分联通块。

这样，按顺序地，我们可以得到某个点的所有可能决策点的转移。

（其实思想有点类似CDQ分治，考虑H到根的路径对后面分治树部分的影响。）

理论O(nlog^2n) 二分的logn同样比较虚。

 

 

法三：

dfs真的不能直接进行吗？

其实可以。

一个厉害的东西是二进制分组。

至于撤销，

类似分块的处理，

如果多了4个1，那么把前两个1合成2，

如果多了4个2，那么把前两个2合成4

。。。

删除暴力干掉这个凸包

这样，每添加2^k个点，才会建造一个2^k的凸包。

每删除2^k个点，才会删除一个2^k的凸包。

所以，凸包的建造复杂度，基本和O(nlogn)同级。

就是往前面的暴力找常数比较大。

复杂度O(nlog^2n)+大常数。