题解：CF475E Strongly Connected City 2
bitset 萌萌题。
思路
首先注意到一个很显然的，如果有环的话，可以通过构造使得环内点互相可达，所以我们先缩点，然后就形成了一个森林，然后对于每颗树单独求解。
容易发现一个东西，对于每个点作为根，枚举它的子树，里面的边（包括这个点到根那一条）都应该是一样的方向，即都是指向儿子或都指向父亲。
原因很显然，因为对于一个联通块来讲如果边都是一样的方向，那么同时翻转贡献是不变的，但如果旁边有指向不一样的联通快翻转后就会有额外贡献，所以对于一个子树来讲肯定是都一样最优，同时由于这些点都是等价点了，所以与其他子树拼接造成的贡献也是最大的（拼接的意思是一个内向子树和一个外向子树）。
这个的贡献是好求的，记
对于一颗树，其贡献就是枚举一个点为根
考虑每个点的 _Find_next(i) 函数就可以查找
给出代码，不过没怎么优化，在
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define getchar() (p1 == p2 && (p2 = (p1 = buf1) + fread(buf1, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf1[1 << 23], *p1 = buf1, *p2 = buf1, ubuf[1 << 23], *u = ubuf;
namespace IO
{
template<typename T>
void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
template<typename T,typename... Args>
void read(T &_x,Args&...others){Read(_x);Read(others...);}
const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
#define pc(x) buf[plen++]=x
#define flush(); fwrite(buf,1,plen,stdout),plen=0;
template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 2e3+10,M = 4e6+10;
int n,m,x,y,head[N],dfn[N],low[N],Cnt,cnt,dep[N],fa[N],col[N],st[N],o,f[N],S[N],siz[N],Col[N],ans,p,sum[N],su;
bitset<N>g;
struct w
{
int to,nxt;
}b[M<<1];
struct w1
{
int x,y;
}A[M];
inline void add(int x,int y)
{
b[++cnt].nxt = head[x];
b[cnt].to = y;
head[x] = cnt;
}
void dfs(int x,int y)
{
st[++cnt] = x,dfn[x] = low[x] = ++Cnt; int sum = 0;
for(int i = head[x];i;i = b[i].nxt)
{
if(b[i].to == y && sum == 0) { sum++; continue; }
if(dfn[b[i].to]) low[x] = min(low[x],dfn[b[i].to]);
else dfs(b[i].to,x),low[x] = min(low[x],low[b[i].to]);
}
if(low[x] == dfn[x])
{
o++,p = 0;
while(st[cnt+1] != x) p++,col[st[cnt]] = o,cnt--;
ans += p*p;
}
}
int find(int x)
{
if(x == f[x]) return x;
return f[x] = find(f[x]);
}
void dfs1(int x,int y,int z)
{
siz[x] = S[x],fa[x] = y; Col[x] = z;// cout<<x<<" %*& "<<y<<" "<<S[x]<<endl;
for(int i = head[x];i;i = b[i].nxt)
if(b[i].to != y)
{
dfs1(b[i].to,x,z),siz[x] += siz[b[i].to];
f[x] += f[b[i].to]+siz[b[i].to]*S[x];
}
}
void dfs2(int x,int y,int z1)
{
f[x] += z1+(siz[Col[x]]-siz[x])*S[x];
int Sum = 0;
for(int i = head[x];i;i = b[i].nxt)
if(b[i].to != y) Sum += f[b[i].to];
for(int i = head[x];i;i = b[i].nxt)
if(b[i].to != y)
dfs2(b[i].to,x,z1+Sum-f[b[i].to]+(siz[Col[x]]-siz[b[i].to]-S[x])*S[x]);
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
for(int i = 1;i <= n;i++) f[i] = i;
for(int i = 1;i <= m;i++) read(x),read(y),add(x,y),add(y,x),A[i].x = x,A[i].y = y;
for(int i = 1;i <= n;i++)
if(!dfn[i]) cnt = Cnt = 0,dfs(i,0),cnt = Cnt = 0;
for(int i = 1;i <= n;i++) head[i] = 0,S[col[i]]++;
for(int i = 1;i <= m;i++)
{
x = col[A[i].x],y = col[A[i].y];
x = find(x),y = find(y);
if(x != y) f[x] = y,add(col[A[i].x],col[A[i].y]),add(col[A[i].y],col[A[i].x]);
}
for(int i = 1;i <= o;i++) f[i] = 0;
for(int i = 1;i <= o;i++)
if(!Col[i])
dfs1(i,0,i),dfs2(i,0,0);
for(int i = 1;i <= o;i++)
{
g.reset(); su = 0; g[0] = 1;
for(int j = head[i];j;j = b[j].nxt)
{
if(fa[i] == b[j].to) g |= (g<<(siz[Col[i]]-siz[i]));
else g |= (g<<siz[b[j].to]);
} int ly = g._Find_next((siz[Col[i]]-S[i])/2-1);
su = ly*(siz[Col[i]]-ly-S[i]);//,cout<<j<<" &*&& "<<i<<" "<<Col[i]<<" ???? "<<siz[Col[i]]-j-S[i]<<endl;
// cout<<i<<" * "<<f[i]<<" "<<su<<endl;
sum[Col[i]] = max(su+f[i],sum[Col[i]]);
}
for(int i = 1;i <= o;i++)
if(Col[i] == i) ans += sum[i];
print(ans); flush();
return 0;
}
/*
f_{i,j}
前i个点互相的都解决了，然后看第i+1个点
先来个暴论，能够成环优先成环
因为此时就都能到了
然后先缩点，然后就是若干联通块了
然后肯定对于一颗数肯定是一个类似拓扑序的东西
肯定有一个点有些点连他，他连一些点
枚举哪个点为根，然后直接f_j表示有j个点连根时最大方案数
转移枚举j，然后看是否选即可，复杂度n^2
注意到一个事实，子树无论是内向还是外向贡献是不变的
然后，唯一的不同就是x*(siz-x)
直接f_i表示是否能凑出i
17 16
15 6
14 1
16 5
2 16
12 5
4 1
4 3
7 6
6 13
10 11
11 5
8 6
9 5
17 16
5 4
4 15
*/