AT_toyota2023spring_final_g Git Gud (tsinsen Di6ns)
图论、树上问题、贪心、Ad-hoc
定义：一个点度数 \(deg_u\) 为被合并次数；一个点集度数 \(deg_S\) 为点集内点与点集外点连边数（一条边即一次合并）
结论1：合并两个连通块 \(A,B\)，答案 += \(\max(deg_A,deg_B)+1\)，将度数小的作为新的根。
结论2：若合并了两个连通块 \(A,B\) 且 \(|A|>1\)，则可以先将 \(B\) 和 \(A\) 中 与 \(B\) 相连的点合并，再按原结构合并 \(A\)，发现 \(B\) 深度增加而其他节点深度不变，答案不会变劣。
推论1：任一时刻只存在最多 \(1\) 个大小 \(>1\) 的连通块。
证明：
利用结论2归纳证明。
结论3：合并连通块 \(A\) 和点 \(u\) 时，\(u\) 一定是新的根。
证明：
若不然（不存在最优解满足结论3），则先将 \(u\) 和 \(A\) 中 \(u\) 指向的点合并，根据结论2，答案不会变劣，不断调整最终总能满足条件。
合并两个连通块时 \(deg_{A\cup B}=deg_A+deg_B-2\)，所以初始令所有点度数 \(-2\)，则 \(deg_{A\cup B}-2=(deg_A-2)+(deg_B-2)\)。答案 += \(\max(deg_A,deg_B)+1\)，考虑在计算过程中暂时去掉 \(+1\)。综上，在答案中加回来 \(3(n-1)\)（\(n-1\) 是合并次数）。
考虑枚举 \(r \in V\) 作为初始连通块。
设点 \(u\) 在第 \(t_u\) 个被合并，则答案为 \(\sum\limits_{i=1}^n(n-t_i)deg_i=n\sum\limits_{i=1}^ndeg_i+\sum\limits_{i=1}^nt_ideg_i\)。变为最小化 \(\sum\limits_{i=1}^nt_ideg_i\)，其中 \(t_u>t_{fa_u}\)，为经典贪心，参考UVA1205 Color a Tree。
贪心：
注意到权值最大的点 \(u\) 一定紧跟在 \(fa_u\) 后加入，则用并查集合并 \(u\) 与 \(fa_u\)。
考虑合并后的点权：设点集 \(S，T\) 已被确定在操作序列上构成连续段，则比较二者之间：
若 \(S\) 在 \(T\) 前，答案+= \(|S|(\sum\limits_{v\in T}w_v)\)。
若 \(T\) 在 \(S\) 前，答案+= \(|T|(\sum\limits_{u\in S}w_u)\)。
移项，改为比较 \(\frac{\sum\limits_{u\in S}w_u}{|S|}\) 和 \(\frac{\sum\limits_{v\in T}w_v}{|T|}\)，用
priority_queue维护（注意到权值不减，惰性删除即可）。
// AT: Git Gud
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
template<typename T>
void chkmin(T &x,const T &y){x=min(x,y);}
template<typename T>
void chkmax(T &x,const T &y){x=max(x,y);}
const int inf=0x3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
const int MOD=998244353;
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;
}
const int N=2005;
int n,fa[N],a[N],w[N],vis[N];
vector<int> G[N];
namespace DSU{int fa[N],sz[N];void init(){for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;}int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);}void merge(int x,int y){fa[y]=x,sz[x]+=sz[y];}
}
using DSU::find,DSU::merge,DSU::sz;
void dfs(int u,int f){fa[u]=f;for(auto v:G[u]){if(v==f) continue;dfs(v,u);}
}
int main(){#ifndef JZQfreopen("dsu.in","r",stdin);freopen("dsu.out","w",stdout);#endifscanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);u++,v++;G[u].push_back(v),G[v].push_back(u);}int ans=-inf;for(int i=1;i<=n;i++){int sum=3*n-3;DSU::init();for(int j=1;j<=n;j++) w[j]=G[j].size()-2,sum+=(n-1)*w[j],vis[j]=0;dfs(i,i);priority_queue<pair<double,int>> pq;for(int j=1;j<=n;j++) if(j!=i) pq.push({(double)w[j],j});while(pq.size()){int u=pq.top().second;pq.pop();if(vis[u]) continue;vis[u]=1;int f=find(fa[u]);sum-=w[u]*sz[f];w[f]+=w[u],merge(f,u);if(f!=i) pq.push({1.0*w[f]/sz[f],f});}chkmax(ans,sum);}printf("%d\n",ans);return 0;
}