CF1179D Fedor Runs for President

yzxoi

发布于 2022-09-19 13:51:09

2470

发布于 2022-09-19 13:51:09

文章被收录于专栏：OI

CF1179D Fedor Runs for President

题目链接：CF1179D

给一棵 n 个点的树，求加入一条边后，最多有多少条无向简单路径。

简单路径定义为任意一个点最多经过一次的路径。

n\leq 5\times 10^5。

Sol

考虑原来的树显然任意两点之间都能抵达，答案为 \frac{n(n-1)}2。

然后加入一条边 (x,y) 就可以把 x 到 y 之间的路径拉出来，显然路径上不同子树间点互相访问的简单路径多了一条，那么答案就增加了 \sum (n-sz_i)\times sz_i，那么题目就转化为了求 \sum sz_i^2 最小。

然后这个东西显然不断向叶节点扩展是更优的，考虑先以 1 为根，找到一个最优解，然后再以这个最优解为根，再跑一遍。接下来就是证明：

考虑 \forall x,y\in[1,n],x\not = y 且 x 为以 1 为根时的最优解，显然 x,y 为两个叶子节点，令 t=\operatorname{lca}(x,y)。

若 z\in 以 t 为根子树，那么可以先不考虑 t 到 1 的贡献，由已知条件可得 (sz_t-sz_x)\times sz_x<(sz_t-sz_y)\times sz_ysz_x<sz_yz 与 x,y 均不属于 t 的同一棵子树内，显然 (x,z) 比 (y,z) 更优，(sz_t-sz_z)\times sz_z+(sz_x-s_t)\times sz_t<(sz_t-sz_z)\times sz_z+(sz_y-s_t)\times sz_t
若 z\not\in 以 t 为根子树，那么同理也可以通过拆贡献的方式得出 (x,z) 比 (y,z) 更优。

然后就类似于求树的直径的方式，两次 DFS 就可以求出答案了，时间复杂度 \mathcal O(N)。

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=5e5+10;
int n,fir[N],nxt[N<<1],son[N<<1],tot,sz[N];
LL Ans[N];
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i]
I void G(CI x,CI fa){
    RI i;for(sz[x]=1,i=fir[x];i;i=nxt[i]) to^fa&&(G(to,x),sz[x]+=sz[to]);
}
I void DFS(CI x,CI fa){
    RI i;for(i=fir[x];i;i=nxt[i]) to^fa&&(Ans[to]=Ans[x]+1LL*(sz[x]-sz[to])*sz[to],DFS(to,x),0);
}
int main(){
    RI i,x,y,Mx;for(read(n),i=1;i<n;i++) read(x,y),Add(x,y),Add(y,x);
    for(G(1,0),Ans[Mx=1]=1LL*n*(n-1)>>1,DFS(1,0),i=1;i<=n;i++) Ans[Mx]<Ans[i]&&(Mx=i);
    for(G(Mx,0),Ans[Mx]=1LL*n*(n-1)>>1,DFS(Mx,0),i=1;i<=n;i++) Ans[Mx]<Ans[i]&&(Mx=i);
    return writeln(Ans[Mx]),0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-08-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs