【Codeforces 1019E】Raining season | Mrsrz's blog

点分治，闵可夫斯基和合并凸包。

题目大意：

给定一棵树，每条边的边权是一个一次函数 $at+b$，$t$ 表示当前的时刻。保证 $a,b\geq 0$。

对于 $t\in[0,m)$，要求出每个整数时刻的树的直径的长度。

题解：

和树上路径有关的问题，可以考虑点分治。

我们考虑当前连通块中，经过分治重心的路径。由于 $a,b\geq 0$，这样的路径的端点一定是叶子。

对于分治重心作为根的每棵子树，都有很多条到根路径，它们的长度也可以用一次函数 $at+b$ 表示。

如果一条路径在任意时刻都不能成为最大值，那么它显然没有任何用，所以我们只需要考虑所有在某个时刻能够成为最大值的路径。

经典套路，将 $at+b$ 映射成平面上的点 $(a,b)$，然后在上凸壳上的点才有可能成为最大值。

我们对于每个分治重心的子树，将它的所有路径排序然后求凸包。

考虑两条来自不同子树的路径 $a_1t+b_1$ 和 $a_2t+b_2$，它们可以合并为 $(a_1+a_2)t+(b_1+b_2)$，对应平面上的点就是 $(a_1+a_2,b_1+b_2)$。我们要求的是最大值，所以只需要合并后在凸包上的点集。

这就是经典的闵可夫斯基和合并凸包的问题，可以在 $O(n+m)$ 的时间复杂度里合并大小为 $n$ 和 $m
$ 的两个凸壳。

但是一个点作为根有很多不同的子树，如果求两两的闵可夫斯基和，那么时间复杂度就不正确了。

可以直接使用边分治来使每次只有两个需要合并的凸包，这样凸包合并的总复杂度就是 $O(n\log ⁡n)$ 的。

如果是点分治的话，考虑当前有 $k
$ 棵子树，就有 $k$ 个凸包。我们需要求出这 $k$ 个凸包的闵可夫斯基和的凸包并。

我们可以对这 $k$ 个凸包进行分治，这样每个凸包的点只会被扫描 $\log ⁡k$ 遍。分治的时候，对于左、右两边的凸包，我们求闵可夫斯基和，向上传递时则是凸包并。将所有闵可夫斯基和得到的凸包再求凸包并即可（这一步可以放到点分治结束后直接一遍合并）。

看上去时间复杂度是 $O(n\log^2⁡n)$ 的，但是这个过程其实和边分治是类似的，所以是 $O(n\log ⁡n)$ 的。

之后就按照刚刚说的，对最后所有的闵可夫斯基和得到的凸包求一个凸包并，然后就可以 $O(m)$ 求每个时刻的答案。

由于点分治里求凸包需要一个排序，这里时间复杂度为 $O(n\log^2⁡n)$，而其它部分的时间复杂度是不高于 $O(n\log^2⁡n)$的。所以算法的总时间复杂度 $O(n\log^2⁡n+m)$。

空间复杂度大概是 $O(n)$，不超过 $O(n\log ⁡n)$。

Code：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
typedef long long LL;
struct point{
    LL x,y;
    inline bool operator<(const point&rhs)const{return x==rhs.x?y>rhs.y:x<rhs.x;}
    inline point operator+(const point&r)const{return(point){x+r.x,y+r.y};}
    inline point operator-(const point&r)const{return(point){x-r.x,y-r.y};}
}sta[N];
int top;
struct hull{
    inline bool cross(point a,point b){return(long double)a.x*b.y-1e-8>(long double)a.y*b.x;}
    std::vector<point>pt;
    inline bool empty()const{return pt.empty();}
    inline void add(int x,LL y){for(auto&i:pt)i.x+=x,i.y+=y;}
    inline void insert(const point&nw){
        while(pt.size()>1){
            const point&pre=pt.back(),&ppre=pt[(int)pt.size()-2];
            if(cross(nw-ppre,pre-ppre)==0)pt.pop_back();else break;
        }
        pt.push_back(nw);
    }
    inline void insert(LL x,LL y){insert((point){x,y});}
    hull operator*(const hull&rhs){
        if(rhs.empty())return*this;
        if(empty())return rhs;
        hull c;
        int i1=0,i2=0;
        for(;i1!=(int)pt.size()-1||i2!=(int)rhs.pt.size()-1;){
            c.insert(pt[i1]+rhs.pt[i2]);
            const point&nw=c.pt.back();
            if(i1==(int)pt.size()-1)++i2;else
            if(i2==(int)rhs.pt.size()-1)++i1;else{
                point _i1=pt[i1+1]+rhs.pt[i2],_i2=pt[i1]+rhs.pt[i2+1];
                if(cross(_i1-nw,_i2-nw)==0)++i1;else ++i2;
            }
        }
        c.insert(pt[i1]+rhs.pt[i2]);
        return c;
    }
    void done(int m){
        int it=0;
        if(empty()){
            while(m--)putchar('0'),putchar(' ');
        }
        for(int i=0;i<m;++i){
            while(it+1<(int)pt.size()&&i*pt[it].x+pt[it].y<=i*pt[it+1].x+pt[it+1].y)++it;
            printf("%lld ",i*pt[it].x+pt[it].y);
        }
    }
    inline void output(){
        for(auto it:pt)printf("(%lld,%lld) ",it.x,it.y);putchar('\n');
    }
};
vector<hull>A;
void merge(hull&a,hull&b){
    hull c;
    auto i1=a.pt.begin(),i2=b.pt.begin();
    while(i1!=a.pt.end()&&i2!=b.pt.end())
    if(i1->x<i2->x||i1->x==i2->x&&i1->y>i2->y)c.insert(*i1++);else c.insert(*i2++);
    while(i1!=a.pt.end())c.insert(*i1++);
    while(i2!=b.pt.end())c.insert(*i2++);
    a=c;
}
struct edge{
    int to,nxt,a,b;
}e[N<<1];
int n,m,nod,rt,sz[N],mxd[N],all,head[N],cnt;
bool vis[N];
void get_centroid(int now,int pre){
    mxd[now]=0,sz[now]=1;
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]&&e[i].to!=pre){
        get_centroid(e[i].to,now),sz[now]+=sz[e[i].to];
        mxd[now]=max(mxd[now],sz[e[i].to]);
    }
    mxd[now]=max(mxd[now],all-sz[now]);
    if(!rt||mxd[now]<mxd[rt])rt=now;
}
void dfs(int now,int pre,LL a,LL b){
    bool x=0;
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre&&!vis[e[i].to]){
        x=1;
        dfs(e[i].to,now,a+e[i].a,b+e[i].b);
    }
    if(!x)sta[++top]=(point){a,b};
}
void mink(vector<hull>&A,int l,int r,hull&x){
    if(l==r)x=A[l];else{
        hull R;
        const int mid=l+r>>1;
        mink(A,l,mid,x),mink(A,mid+1,r,R);
        ::A.push_back(x*R);
        merge(x,R);
    }
}
void work(int now){
    vector<hull>B;
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
        top=0;
        dfs(e[i].to,now,e[i].a,e[i].b);
        sort(sta+1,sta+top+1);
        hull x;
        for(int i=1;i<=top;++i)x.insert(sta[i]);
        B.push_back(x);
    }
    if(B.empty())return;
    hull k;
    mink(B,0,(int)B.size()-1,k);
    A.push_back(k);
}
void solve(int now){
    vis[now]=1;
    work(now);
    int sm=all;
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
        all=sz[now]>sz[e[i].to]?sz[e[i].to]:sm-sz[now];
        rt=0;
        get_centroid(e[i].to,now);
        solve(rt);
    }
}
void final(vector<hull>&A,int l,int r,hull&x){
    if(l==r)x=A[l];else{
        const int mid=l+r>>1;
        hull R;
        final(A,l,mid,x),final(A,mid+1,r,R);
        merge(x,R);
    }
}
int main(){
    scanf("%d%d",&n,&m),nod=n;
    for(int i=1;i<n;++i){
        int u,v,a,b;
        scanf("%d%d%d%d",&u,&v,&a,&b);
        e[++cnt]=(edge){v,head[u],a,b},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],a,b},head[v]=cnt;
    }
    all=n,rt=0;
    get_centroid(1,0);
    solve(rt);
    hull k;
    if(!A.empty())final(A,0,(int)A.size()-1,k);
    k.done(m);
    return 0;
}