好的证明复杂度是：
对于度数大于根号的点，最多根号个。称为大点。
度数小于根号的点，称为小点。
对于小点，边怎么定向不关心。之后度数最多根号个
对于大点，和小点的边一定是被小点指过来，只可能保留指向大点的出边。之后度数最多根号个。
复杂度本质是考虑每个点会被二次枚举多少次。也就是入边个数。
入边个数总共是m，每个点度数小于根号m
所以总复杂度是msqrt(m)
挺暴力的做法，
依靠对三元环无向边的定向，使得暴力枚举的复杂度其实是O(msqrt(m))
一些挺复杂的图的东西有时候可以根据度数分块考虑来优化暴力
但是这个做法巧妙之处按照度数定向，是可以通过度数的大小证明复杂度。。
例题：
PA2009 Cakes
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=100000+5;
int n,m;
int a[N];
struct node{
int nxt,to;
}e[250000+5];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int du[N];
int b[250000+5][2];
ll ans=0;
int vis[N];
int main(){
rd(n);rd(m);
for(reg i=1;i<=n;++i) rd(a[i]);
for(reg i=1;i<=m;++i){
rd(b[i][0]);rd(b[i][1]);
++du[b[i][0]];++du[b[i][1]];
}
for(reg i=1;i<=m;++i){
int x=b[i][0],y=b[i][1];
if(du[x]<du[y]||(du[x]==du[y]&&x<y)) swap(x,y);
add(x,y);
}
for(reg x=1;x<=n;++x){
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
vis[y]=x;
}
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
for(reg j=hd[y];j;j=e[j].nxt){
int z=e[j].to;
if(vis[z]==x) ans+=max(max(a[x],a[y]),a[z]);
}
}
}
printf("%lld",ans);
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/3/6 14:12:52
*/
bzoj5407 girls
大力容斥
附疑问：
有向图三元环计数比较好的做法？
不知。（可以bitset）
有时候，在DAG枚举路径转移的时候，重新定向可以暴力枚举前驱或者后继，复杂度就有了保证
upda：2019.5.6
四元环计数？一共有三种情况
本做法不用分类讨论.
给每个点分配一个rank ,rki<rkj当且仅当deg_i<deg_j或deg_i==deg_j&&i<j
建立新边,rk小的连向rk大的
显然是DAG
一个环有三种情况
枚举u，走原边到v，再走新边到w，如果rk(u)<rk(w)，那么ans+=cnt[w],++cnt[w]
cnt每次枚举u完了之后要清空.
三种情况都会恰好被计算一次