CF 1019E Raining season 边分治

题意

一颗树，每条边在第 $i$ 天的长度为 $a * i + b$ ，求第 $i$ 天的直径

题解

这题好难。。。。
首先直径的表达式一定是形如 $\sum a * i + \sum b$ 的形式
也就是一条直线的表达式
最暴力的方法，求出所有的路径的表达式，每一天挑一个最大的输出即可
有没有快速找到最大的方法呢？有的
类似斜率优化，我们维护这样一个东西

这样的话，就可以 $O (1)$ 找到最大值了
所以产生了第一个问题，如何在一堆直线中维护出一个下凸壳

这个问题可以转化为，将 $(a, b)$ 看做二维平面的点后，维护一个上凸壳，如图

证明：
设三条直线的表达式为 $y = k_{i} * x + b_{i}$

我们需要维护的是，交点2在交点1的右侧
交点1 的表达式为 $x_{1} = \frac{b_{1} - b_{2}}{k_{2} - k_{1}}, y_{1} = k_{1} * x_{1} + b_{1}$
交点2 的表达式为 $x_{2} = \frac{b_{2} - b_{3}}{k_{3} - k_{2}}, y_{2} = k_{2} * x_{2} + b_{2}$
令 $x_{2} > x_{1}$ 得
$(b_{2} - b_{3}) * (k_{2} - k_{1}) - (b_{1} - b_{2}) * (k_{3} - k_{2}) > 0$
发现，这就是2个向量叉乘的表达式，所以就是维护一个下凸壳
要注意的是只有下凸壳的右半部分，因为要保证 $k$ 递增 $b$ 递减
问题一解决

我们发现，路径的条数是 $n^{2}$ 的级别的，无法找出所有的路径
边分治登场
对于枚举到的边，找出经过它的直径的可能
假设枚举的边为 $(u, v)$
首先找出从 $u$ 出发能到达点的距离表达式，维护一个上凸壳，这是显然可以的，可以保证正确性，它的必要性后文会提到
同样对 $v$ 进行预处理
那么需要对路径进行合并，针对凸壳的合并，有一个算法叫闵可夫斯基和凸包
可以在线性的时间进行合并
然后将合并完的路径放到一个队列里，表示候选答案
最后，对候选答案再求一次上凸壳，就能得到答案了

复杂度
时间，因为求凸包时要排序，所以是 $O (n l o g^{2} n)$
空间，候选的直线有 $O (n l o g n)$ 条，所以为 $O (n l o g n)$

反思
注意模板的变化， $M i n k o w s k i$ 时，注意求的是上凸还是下凸！！！
输出答案的时候，答案不是一定在第 $i$ 或 $i + 1$ 条之间

上面的情况，就是相邻两个交点全都在两个相邻整数之间！！！！

代码

#include<bits/stdc++.h>
#define N 400010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef  pair<int,int> pp;
int cnt=1,n,m,tot,tn,sn,ct,sa,sb,mn,fg,la[N],sz[N],del[N];
struct Point{
    LL x,y;
    Point(LL x=0,LL y=0):x(x),y(y){}
    inline Point operator + (const Point c)const{return Point(x+c.x,y+c.y);}
    inline Point operator - (const Point c)const{return Point(x-c.x,y-c.y);}
    inline friend long double Cross(Point a,Point b) {return (long double)a.x*b.y-(long double)a.y*b.x;}
    bool operator < (const Point z) const{return x==z.x?y>z.y:x<z.x;}
}q[N*19],A[N],B[N],zero(0,0);
struct edge{int from,to,x,y,nxt; }G[N];
struct node{int u,x,y;};
vector<node>a[N];
inline void add(int u,int v,int x,int y){ G[++cnt]={u,v,x,y,la[u]}; la[u]=cnt; }
void Minkowski(Point *a,int n,Point *b,int m){
    int x=1,y=1;
    q[tot++]=a[0]+b[0]; 
    while(x<n&&y<m)
        if (Cross(a[x]-a[x-1],b[y]-b[y-1])<0) 
            q[tot]=q[tot-1]+a[x]-a[x-1],tot++,x++;
        else
            q[tot]=q[tot-1]+b[y]-b[y-1],tot++,y++;
    while(x<n) q[tot]=q[tot-1]+a[x]-a[x-1],tot++,x++;
    while(y<m) q[tot]=q[tot-1]+b[y]-b[y-1],tot++,y++;
}
int Convex( Point *a,int n){
    sort(a,a+n);
    int k=-1,m=0;LL mn=0;
    int tmp=0;
    for(int i=1;i<n;i++) if (a[i].x!=a[tmp].x) a[++tmp]=a[i]; n=tmp+1;
    for(int i=0;i<n;i++) if(a[i].y>=mn) mn=a[i].y,k=i;
    for(int i=k;i<n;i++){
        while(m>1&&Cross(a[m-1]-a[m-2],a[i]-a[m-2])>=0) m--;
        a[m++]=a[i];
    }
    return m;
}

void rebuild(int x,int fa){
    int pre=0;
    for(auto i:a[x]){
        int v=i.u,w=i.x,t=i.y;
        if (v==fa) continue;
        if (!pre){
            add(x,v,w,t),add(v,x,w,t); pre=x;
        }else{
            int k=++tn;
            add(k,v,w,t), add(v,k,w,t);
            add(k,pre,0,0), add(pre,k,0,0);
            pre=k;
        }
        rebuild(v,x);
    }
}
void findct(int x,int fa){
    sz[x]=1;
    for(int i=la[x];i;i=G[i].nxt){
        int v=G[i].to;
        if (del[i>>1]||v==fa) continue;
        findct(v,x); sz[x]+=sz[v];
        int tmp=max(sz[v],sn-sz[v]);
        if (tmp<mn){ct=i; mn=tmp; }
    }
}

void gao(int x,int fa,LL a,LL b){
    if (x<=n) if (!fg)A[sa++]={a,b}; else B[sb++]={a,b};
    for(int i=la[x];i;i=G[i].nxt) if (!del[i>>1]&&G[i].to!=fa)
        gao(G[i].to,x,a+G[i].x,b+G[i].y);
}

void dfs(int x){
    int u=G[x].from,v=G[x].to;
    if (sz[u]<sz[v]) swap(u,v);
    del[x>>1]=1;
    sa=1; fg=0; A[0]=zero; gao(u,-1,0,0);           sa=Convex(A,sa);
    sb=1; fg=1; B[0]=zero; gao(v,-1,G[x].x,G[x].y); sb=Convex(B,sb);
    Minkowski(A,sa,B,sb);
    int tot=sn;
    sn=tot-sz[v]; mn=INF; findct(u,-1); if (mn!=INF)dfs(ct);
    sn=sz[v];     mn=INF; findct(v,-1); if (mn!=INF)dfs(ct);
}
int main(){
    scc(n,m);
    int pre=0;
    for(int i=1,u,v,x,y;i<n;i++){
        scc(u,v);scc(x,y);
        if (!pre) pre=u;
        a[u].pb({v,x,y}); a[v].pb({u,x,y});
    }
    tn=n;
    rebuild(1,-1);
    sn=tn; mn=INF; findct(1,-1); dfs(ct);
    tot=Convex(q,tot);
    int k=0; q[tot].x=q[tot].y=-INF;
    for(LL i=0;i<m;i++){
        while(q[k+1].x*i+q[k+1].y>=q[k].x*i+q[k].y) k++;
        printf("%lld ",q[k].x*i+q[k].y);
    }
    return 0;
}