题解 CF1179D 【Fedor Runs for President】

· · 题解

CF1179D Fedor Runs for President解题报告

更好的阅读体验

题意

分析

树上斜率优化好题。

先讲一下定义：size_x为x的子树大小，sons_x为x的儿子数量，son(x)指x所有儿子形成的集合，path(x,y)指x到y路径上所有点形成的集合。

因为树上每两个点有且仅有一条路径，所以原本树上的路径数量为\frac{n(n-1)}{2}，然后考虑添加一条边会增加多少条无向简单路径：

假如我们将要添加(x,y)，那么我们先提出x到y的路径，假如k在路径上，我们称s_k为以k为根，不向路径上扩展的子树大小。那么我们可以知道每一颗这样的子树之间都多了一条路径，根据乘法原理有这条边对答案贡献为\frac{\sum_{k\in path(x,y)}(n-s_k)\cdot s_k}{2}（除2是为了去重）。

变一下型：

\frac{\sum_{k\in path(x,y)}(n-s_k)\cdot s_k}{2} =\frac{\sum_{k\in path(x,y)}(n\cdot s_k-s_k^2)}{2} =\frac{n\cdot \sum_{k\in path(x,y)}s_k-\sum_{k\in path(x,y)}s_k^2}{2} =\frac{n^2-\sum_{k\in path(x,y)}s_k^2}{2}

那么我们的目的找到一条路径path(x,y)，让\sum_{k\in path(x,y)}s_k^2最小。

我们运用点分治的思想，考虑枚举每一个点x，计算x子树中，每一条经过x的路径的答案。

设f_x为从x到x子树中任意结点，且满足让上式最小的路径，那么很容易列出转移方程：

f_x=\min_{y\in son(x)}\{f_y+(size_x-size_y)^2\}

解释一下，size_x-size_y相当于s_x（因为x的儿子y在路径上）。

这个转移方程很显然，也很容易在O(n)的复杂度中求出。

size[x]=1;
for(int i=start[x];i;i=then[i]){
    int y=to[i];
    if(y==last)
        continue;
    dfs(y,x);
    size[x]+=size[y];
}
f[x]=size[x]*size[x];
for(int i=start[x];i;i=then[i]){
    int y=to[i];
    if(y==last)
        continue;
    f[x]=min(f[x],f[y]+(size[x]-size[y])*(size[x]-size[y]));
    p[++ps]=y;
}

然后考虑x子树中，每一条经过x的路径，设这条路径经过两个x的儿子y,z，那么我们可以把f_y代表的路径，f_z代表的路径和x拼起来计算答案。

我们枚举两个儿子：

ans=\min_{y\in son(x),z\in son(x),y\ne z}\{f_y+f_z+(n-size_y-size_z)^2\}

同样解释一下，n-size_y-size_z是除了y子树和z子树中的结点外所有的结点，因为x,y,z在均路径上，所以其他的点都必须分配到x子树中，即s_x=n-size_y-size_z。

枚举它的复杂度就是O(sons_x^2)了，加上dfs，复杂度肯定无法通过本题。

考虑树上斜率优化，我们枚举x的儿子y，然后在斜率优化中求出决策点z。

套路性地枚举两个决策点size_q\leqslant size_p，且p比q更优，即f_y+f_p+(n-size_y-size_p)^2\leqslant f_y+f_q+(n-size_y-size_q)^2。

拆开平方，消掉相同的项就可以得到f_p+size_p^2-2(n-size_y)\cdot size_p\leqslant f_q+size_q^2-2(n-size_y)\cdot size_q。

套路性变形：(f_p+size_p^2)-(f_q+size_q^2)\leqslant 2(n-size_y)(size_p-size_q)。

因为size_p\geqslant size_q，那么除过来不变号，化成斜率式：\frac{(f_p+size_p^2)-(f_q+size_q^2)}{size_p-size_q}\leqslant 2(n-size_y)。

注意如果size_p=size_q需要特判一下：

inline int x(int p){
    return size[p];
}
inline int y(int p){
    return f[p]+size[p]*size[p];
}
inline double slope(int a,int b){
    if(x(a)==x(b))
        return y(a)>y(b)? inf:-inf;
    return 1.0*(y(a)-y(b))/(x(a)-x(b));
}

我们在斜率优化之前给所有儿子按照size排一下序，就可以上斜率优化板子了。

我们分析一下时间复杂度：对于每个点，复杂度的瓶颈就是遍历到后面的所有儿子和给它所有儿子\text{sort}一遍。

先证明一个引理：a\log a+b\log b\leqslant(a+b)\log(a+b)

不妨设a\geqslant b，那么a\log a+b\log b\leqslant a\log a+b\log a=(a+b)\log a\leqslant (a+b)\log(a+b)。

对于排序，它的复杂度都是O(n\log n)的，因此我们可以直接看做每个点x都需要O(sons_x\log sons_x)的处理。

然后，我们处理递归：

可以按照深度归纳，我们证明对于x，处理它的复杂度一定是O(size_x\log size_x)的。

首先对于叶子结点一定成立，因为处理它的复杂度就是O(1)的。

对于非叶子结点x，假如它的儿子是y_1\cdots y_k，且它每个儿子都满足这个复杂度约束，那么处理它儿子的总复杂度为size_{y_1}\log size_{y_1}+size_{y_2}\log size_{y_2}+\cdots+size_{y_k}\log size_{y_k}，按照上面的引理一直处理下去，就可以得到上式小于等于(size_{y_1}+\cdots+size_{y_k})\log (size_{y_1}+\cdots+size_{y_k})，因为size_x=size_{y_1}+\cdots+size_{y_k}+1，所以递归所有儿子的复杂度是O(size_x\log size_x)的。

再加上排序的复杂度，便可以得出处理x的复杂度是O(size_x\log size_x)的。

我们从1开始\text{dfs}，那么由上面的证明可以知道处理1的时间复杂度为O(size_1\log size_1)。

即总复杂度为O(n\log n)。

代码

#include<stdio.h>
#include<algorithm>
#define int long long
#define inf 1000000000000000000
using namespace std;
const int maxn=500005,maxm=1000005;
int i,j,k,m,n,e,ans=inf;
int start[maxn],to[maxm],then[maxm],f[maxn],size[maxn],p[maxn],q[maxn];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
inline bool cmp(int a,int b){
    return size[a]<size[b];
}
inline int x(int p){
    return size[p];
}
inline int y(int p){
    return f[p]+size[p]*size[p];
}
inline double slope(int a,int b){
    if(x(a)==x(b))
        return y(a)>y(b)? inf:-inf;
    return 1.0*(y(a)-y(b))/(x(a)-x(b));
}
void dfs(int x,int last){
    int ps=0,l=1,r=0;
    size[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
        size[x]+=size[y];
    }
    f[x]=size[x]*size[x];
    if(size[x]==1)
        return ;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        f[x]=min(f[x],f[y]+(size[x]-size[y])*(size[x]-size[y]));
        p[++ps]=y;
    }
    ans=min(ans,f[x]+(n-size[x])*(n-size[x]));
    sort(p+1,p+1+ps,cmp);
    q[++r]=p[1];
    for(int i=2;i<=ps;i++){
        while(l<r&&slope(q[l+1],q[l])<=2*(n-size[p[i]]))
            l++;
        ans=min(ans,f[p[i]]+f[q[l]]+(n-size[p[i]]-size[q[l]])*(n-size[p[i]]-size[q[l]]));
        while(l<r&&slope(p[i],q[r-1])<=slope(q[r],q[r-1]))
            r--;
        q[++r]=p[i];
    }
}
signed main(){
    scanf("%lld",&n);
    for(i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    printf("%lld\n",n*(n-1)/2+(n*n-ans)/2); 
    return 0;
}