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;
}