CF1179D Fedor Runs for President解题报告

解题报告

---

CF1179D Fedor Runs for President解题报告

更好的阅读体验

题意

• 定义简单路径为任意一个点仅经过一次的路径。
• 给定一颗$n$个点的树，求添加一条边后最多有多少无向简单路径。
• 数据范围：$2\leqslant n\leqslant 5\cdot 10^5$

分析

树上斜率优化好题。

先讲一下定义：$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;
}