【CodeForces1019E】Raining season（边分治+斜率优化）

程序员文章站 2022-06-04 09:23:49

...

题目大意

有n个结点的一棵树，每条边有两个权值a,b，第t天经过第i条边花费时间 $a_{i} t + b$ ，给定m，求 $t = 0, 1, 2... m - 1$ 时，最长的路径长度。

题解

简介边分治

类似点分治选择重心，边分治选择一条边，把树分成两边，使得两边的点数最接近。
但对普通的树进行边分治容易退化，如下面这种图会退化为 $O (n)$ （官方题解称为star tree）
【CodeForces1019E】Raining season（边分治+斜率优化）
所以使用边分治，需要将一般树，转化为二叉树，这样边分治分成的两块，保证了两块的节点数一定在 $[\frac{n}{3}, \frac{n}{2}]$ 之间。

边分治相对于点分治的优点在于，它只会把树分成两块，在有些情况下，合并结果时，减少大量代码量。

本题的边分治

在多叉树转二叉树时，对于本题，我们必须保证任意两点的距离不变，转二叉时需要新建节点，如下图：
【CodeForces1019E】Raining season（边分治+斜率优化）

对于边分治的一棵数，计算每个子树的大小siz[u]，找到最大的子树并且大小 < 总大小的一半，选择这个结点和它父亲结点的边作为重心边，分成两棵树。

对于分成的两棵树
易知，最长路经一定是从根走到叶子节点的路径，统计所有路径，把a值和b值分别加起来，得到这条路径的函数 $a t + b$ 。

这两棵树，我们都可以得到一大堆路径的函数，合并两个路径即分别相加他们的a值和b值，现在考虑如何 $O (n)$ 合并所有路径。
设 $a_{i} < a_{j}$

a_{i} t + b_{i} < a_{j} t + b_{j}

- (b_{j} - b_{i}) < (a_{j} - a_{i}) t

\frac{b_{j} - b_{i}}{a_{j} - a_{i}} > - t

对于每个函数 $a t + b$ ，将其看作一个点 $(a, b)$ ，根据斜率式，将维护上凸包，斜率递减（不懂可见斜率优化）

将分成的两棵树分别得到的所有路径函数，分别建立两个凸包。
合并时，用两个变量x,y，表示当前合并到这两个凸包的第几个结点，每次判断x与x+1的斜率k1，y与y+1的斜率k2，选择斜率更大的+1，再将新的x结点与y结点合并（选择斜率大的合并，保证了在新凸包中斜率变化量更小，才能使凸包中结点不漏选）

做完边分治，我们得到了整棵树所有有用路径的函数凸包，已经保证了答案的单调，直接计算即可。

代码

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=200005,MAXM=MAXN*3;

struct Edge
{
    int v,a,b,id;
    Edge()=default;
    Edge(int _v,int _a,int _b,int _id):v(_v),a(_a),b(_b),id(_id) {}
};

class Tree
{
public:
    int n;
    vector<Edge> adj[MAXN*2];

    vector<Edge> &operator [] (unsigned int i)
    {
        return adj[i];
    }
    void AddEdge(int u,int v,int a,int b,int i)
    {
        adj[u].emplace_back(v,a,b,i);
        adj[v].emplace_back(u,a,b,i);
    }
};

struct Path
{
    long long a,b;
    Path()=default;
    Path(long long _a,long long _b):a(_a),b(_b) {}
    bool operator < (const Path &t)const
    {
        return a<t.a||(a==t.a&&b<t.b);
    }
};

int N,M,edgeid;
Tree F,G;

void ToBinaryTree(int u,int fa=0)
{
    int last=u;
    for(const auto &e:F[u])
        if(e.v!=fa)
        {
            G.AddEdge(last,++G.n,0,0,++edgeid);//fprintf(stderr,"[%d->%d: 0,0]\n",last,G.n);
            G.AddEdge(G.n,e.v,e.a,e.b,++edgeid);//fprintf(stderr,"[%d->%d: %d,%d]\n",G.n,e.v,e.a,e.b);
            last=G.n;
            ToBinaryTree(e.v,u);
        }
}

bool disable[MAXM];
int siz[MAXN];
Edge E[MAXN];
void GetSize(int u,int fa=0)
{
    siz[u]=1;
    for(const auto &e:G[u])
        if(e.v!=fa&&!disable[e.id])
        {
            E[e.v]=Edge(u,e.a,e.b,e.id);
            GetSize(e.v,u);
            siz[u]+=siz[e.v];
        }
}
int FindCentroid(int u,int lim,int fa=0)
{
    if(siz[u]<=lim)
        return u;
    int mxsiz=0,id;
    for(const auto &e:G[u])
        if(e.v!=fa&&!disable[e.id])
        {
            int tmp=FindCentroid(e.v,lim,u);
            if(siz[tmp]>mxsiz)
                mxsiz=siz[tmp],id=tmp;
        }
    return id;
}

void GetPath(int u,vector<Path> &P,Path now=Path(0,0),int fa=0)
{
    if(G[u].size()==1)
        P.push_back(now);
    for(const auto &e:G[u])
        if(e.v!=fa&&!disable[e.id])
            GetPath(e.v,P,Path(now.a+e.a,now.b+e.b),u);
}

void Process(vector<Path> &P)
{
    static vector<Path> tmp;
    sort(P.begin(),P.end());
    tmp.resize(P.size());
    tmp.emplace_back(0,0);
    int top=0;
    for(const auto &p:P)
    {
        while(top>0&&(p.a==tmp[top].a&&p.b>=tmp[top].b))
              top--;
        if(p.a==tmp[top].a&&p.b<=tmp[top].b)
            continue;
        while(top>0&&1.0*(tmp[top].b-tmp[top-1].b)/(tmp[top].a-tmp[top-1].a)<1.0*(p.b-tmp[top].b)/(p.a-tmp[top].a))
            top--;
        tmp[++top]=p;
    }
    for(int i=0; i<=top; i++)
        P[i]=tmp[i];
    P.resize(top+1);
}

vector<Path> P1,P2,P;

void CentroidDecomposition(int u)
{
    GetSize(u);
    if(siz[u]<=1)
        return;
    int centroid1=FindCentroid(u,siz[u]/2);
    int centroid2=E[centroid1].v;

    disable[E[centroid1].id]=true;
    P1.clear();
    P2.clear();
    P1.emplace_back(0,0);
    P2.emplace_back(0,0);
    GetPath(centroid1,P1);
    GetPath(centroid2,P2);

    Process(P1);
    Process(P2);

    int x=0,y=0;
    while(x<(int)P1.size()&&y<(int)P2.size())
    {
        P.emplace_back(P1[x].a+P2[y].a+E[centroid1].a,P1[x].b+P2[y].b+E[centroid1].b);
        double k1=-1e100,k2=-1e100;
        if(x<(int)P1.size()-1)
            k1=1.0*(P1[x+1].b-P1[x].b)/(P1[x+1].a-P1[x].a);
        if(y<(int)P2.size()-1)
            k2=1.0*(P2[y+1].b-P2[y].b)/(P2[y+1].a-P2[y].a);
        if(k1>k2)
            x++;
        else
            y++;
    }

    CentroidDecomposition(centroid1);
    CentroidDecomposition(centroid2);
}

int main()
{
    scanf("%d%d",&N,&M);
    F.n=N;
    for(int i=1; i<N; i++)
    {
        int u,v,a,b;
        scanf("%d%d%d%d",&u,&v,&a,&b);
        F.AddEdge(u,v,a,b,i);
    }

    G.n=N;
    ToBinaryTree(1);

    P.emplace_back(0,0);
    CentroidDecomposition(1);
    Process(P);

    int id=0;
    for(int t=0; t<M; t++)
    {
        while(id<(int)P.size()-1&&(1LL*t*P[id+1].a+P[id+1].b)>(1LL*t*P[id].a+P[id].b))
            id++;
        long long ans=1LL*t*P[id].a+P[id].b;
        printf("%I64d ",ans);
    }
    puts("");

    return 0;
}