CF1179D Fedor Runs for President
题目链接：CF1179D
给一棵 n 个点的树，求加入一条边后，最多有多少条无向简单路径。
简单路径定义为任意一个点最多经过一次的路径。
nleq 5times 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,yin[1,n],xnot = y 且 x 为以 1 为根时的最优解，显然 x,y 为两个叶子节点，令 t=operatorname{lca}(x,y)。
- 若 zin 以 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
- 若 znotin 以 t 为根子树，那么同理也可以通过拆贡献的方式得出 (x,z) 比 (y,z) 更优。
然后就类似于求树的直径的方式，两次 DFS 就可以求出答案了，时间复杂度 mathcal O(N)。
代码语言：javascript复制#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 '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;
}
