虚高 *2800。放模拟赛 T2 人均切了。
先想树的情况怎么做。枚举每个起点，剩下的贡献就是定值。求这个值可以钦定 \(1\) 为根求出所有的 \(siz\)，然后枚举 \(i\) 为起点，以 \(i\) 为起点的答案就是 \(\sum siz_i\) 加上 \(i\) 到 \(1\) 路径上，不含 \(1\) 的所有点的 \(\sum_j n-2\times siz_j\)。
然后放到基环树上，发现需要注意环的情况，在一个环上先往一个方向走和另一个方向的贡献是不一样的。发现可以通过一个环上的区间 dp 解决。
对于环上一个点 \(i\) 的贡献，我们只考虑一个在环上，且不在起点所对应环上的点且不为 \(i\) 的点 \(j\)，当染黑 \(j\) 时，\(i\) 造成的贡献。
设环上点编号为 \(0,1,\cdots ,k-1\)，对应点分别为 \(a_0,a_1,\cdots,a_{k-1}\),\(dp_{i,j}\) 为环上编号为 \(i\) 的点开始的一段长为 \(j\) 的区间的最大贡献，则有 \(dp_{i,j}=\max(dp_{i,j-1}+(j-2)\times siz_{a_{i+j-1}},dp_{(i+1)\bmod k,j-1}+(j-2)\times siz_{a_i})\)。其中 \(siz\) 是将在环上的点视为根的 \(siz\)。
初始值 \(dp_{i,1}\) 可以根据上面计算树的方法，得到以 \(i\) 为根的子树内每个点为起点的答案，再取 \(\max\)。
发现空间会炸，于是滚动一下。能过。\(O(n^2)\)。
code：
点击查看代码
int n,m;
int tot,head[N];
struct node{int to,nxt;}e[N<<1];
il void add(int u,int v){e[++tot]={v,head[u]},head[u]=tot;}
namespace s1{
int siz[N],fa[N];
void dfs1(int u,int f){
siz[u]=1,fa[u]=f;
go(i,u){
int v=e[i].to;
if(v==f)continue;
dfs1(v,u),siz[u]+=siz[v];
}
}
void solve(){
dfs1(1,0);
int sum=0;
rep(i,1,n)sum+=siz[i];
int ans=0;
rep(i,1,n){
int x=sum,u=i;
while(u!=1)x+=n-2*siz[u],u=fa[u];
ans=max(ans,x);
}
printf("%d\n",ans);
}
}
namespace s2{
int k,cyc,siz[N],dep[N],fa[N],dp[N][2],id[N];
bool vis[N],inc[N];
vector<int> g;
void dfs1(int u,int f){
vis[u]=1,dep[u]=dep[f]+1,fa[u]=f;
go(i,u){
int v=e[i].to;
if(vis[v]){
if(v!=f)cyc=(i+1)/2;
continue;
}
dfs1(v,u);
}
}
void find_cyc(int u,int v){
vector<int> h;
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v])g.eb(u),u=fa[u];
while(u!=v)g.eb(u),h.eb(v),u=fa[u],v=fa[v];
g.eb(u);
while(h.size())g.eb(h.back()),h.pop_back();
}
void dfs2(int u,int f){
siz[u]=1,fa[u]=f;
go(i,u){
int v=e[i].to;
if(v==f||inc[v])continue;
dfs2(v,u),siz[u]+=siz[v];
}
}
void solve(){
dfs1(1,0),find_cyc(e[cyc*2-1].to,e[cyc*2].to);
for(int i=0;i<(int)g.size();i++)inc[g[i]]=1,id[g[i]]=i;
for(int i:g)dfs2(i,0);
k=g.size();int sum=0;
rep(i,1,n)sum+=siz[i];
rep(i,1,n){
int x=sum,u=i;
while(!inc[u])x+=n-2*siz[u],u=fa[u];
dp[id[u]][1]=max(dp[id[u]][1],x+n-siz[u]);
}
rep(len,2,k){
int p=len&1;
rep(i,0,k-1)dp[i][p]=0;
rep(i,0,k-1){
int j=(i+len-1)%k;
dp[i][p]=max(dp[i][p^1]+siz[g[j]]*(len-2),dp[(i+1)%k][p^1]+siz[g[i]]*(len-2));
}
}
int ans=0;
rep(i,0,k-1)ans=max(ans,dp[i][k&1]);
printf("%d\n",ans);
}
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n){
int u=read()+1,v=read()+1;
add(u,v),add(v,u);
}
s2::solve();
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}