CF1179D Fedor Runs for President

(Updated: )
oi

题目链接：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)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}