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_y$,那么可得 $sz_x<sz_y$,那么显然若 $z$ 与 $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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇