CF1179D Fedor Runs for President

Cocoly1990 · 2021-08-23 09:30:05 · 题解

一道斜率优化的好题，别的题解也说得很清楚了，容斥一下单调队列维护凸壳一下就好了，但明显的斜率优化相对于下面的做法比较复杂。

首先考虑猜结论，显然手玩样例会发现最后都是一条链加上一条边构成一个环，我们设 siz_x 是 x 的子树大小，如果连接了 u,v，那么该路径上不同子树之间的点相互访问的简单路径增加了一条，那么答案增加了 \sum\left(n-size\left[i\right]\right)\times size\left[i\right]，i 是该路径上的点。

显然要最小化 \sum size\left[i\right]^2，然后易证连接的点必然是叶子或根，否则使其再向子树扩展得到的 \sum size\left[i\right]^2 更小。

那么根据λᴉʍ大佬的说法，我们用求直径的方法求两次就好了。关于为什么这么可以，我一时间也没有很好地证明。其实关于直径的方法我也是看了题解才知道，最开始的思路只停留在上面。如果希望正解的还是最好去写斜率优化，可以看出最后树的直径相较于斜率优化在运行时间上差很多。

贴个Code吧，Pre() 是关于子树的处理，dfs() 是答案的统计，存树用的是链式前向星

#include<bits/stdc++.h>
#define ll long long
#define vv (e[i].v)
#define Maxn 500007
inline int read(){
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
using namespace std ;
ll n , head[Maxn] , tot , ans[Maxn] , siz[Maxn] , u , v , Maxi ;
struct Edge
{
    int v , next ;
}e[Maxn << 1] ;
void add(int u , int v)
{
    e[++ tot].v = v ;
    e[tot].next = head[u] ;
    head[u] = tot ;
}
void Pre(int now , int last)
{
    siz[now] = 1 ;
    for(int i = head[now] ; i ;i = e[i].next)
    {
        if(vv == last) continue ;
        Pre(vv , now) ;
        siz[now] += siz[vv] ;
    }
}
void dfs(int now , int last)
{
    for(int i = head[now] ; i ;i = e[i].next)
    {
        if(vv == last) continue ;
        //Pre(vv , now) ;
        ans[vv] = ans[now] + (siz[now] - siz[vv]) * siz[vv] ;
        dfs(vv , now) ;
    }   
}
void MaxF()
{
    Maxi = 1 ;
    for(int i = 1 ; i <= n ; i ++) Maxi = (ans[Maxi] < ans[i]) ? i : Maxi ;
}
int main()
{
    n = read() ;
    for(int i = 1 ; i <= n - 1 ; i ++)
    {
        u = read() ; v = read() ;
        add(u , v) ;
        add(v , u) ;
    }
    Pre(1 , -1) ;
    ans[1] = n * (n - 1) / 2 ;
    dfs(1 , -1) ;
    MaxF() ;
    Pre(Maxi , 0) ;
    ans[Maxi] = ans[1] ;
    dfs(Maxi , 0) ;
    MaxF() ;
    cout << ans[Maxi] ;
    return 0 ; 
}