复杂问题
题目链接：ybt高效进阶 21161
题目大意
给你一个无向图，我们定义一个四元环为一个四个点的集合，这四个点（u,v,x,y）构成的子图，存在边 (u,v),(v,x),(x,y),(y,u)。
然后点有点权，四元环的点权就是那四个点的点权之和。
然后要你求这个图所有四元环的点权和。
思路
在做这道题之前呢，先做做这道题：
无向图三元环计数
（下文默认会了上面的方法）
显然就是把三元环变成了四元环。
那我们考虑用一种叫做 MIM（Meet In Middle）的方法。
好吧其实就算是折半搜索的折半思想。
我们可以类似三元环的做法，然后看看怎么搞。
那它肯定就是这两种结构，我们分别叫它情况一和情况二。
对于情况一，我们可以先走两步，然后记录第三个点确定的时候，有多少种走法，中间点的权值和是多少。然后你再枚举第三个点（应该不能直接 (1sim n)？没试过，但最好用一个数组装着有走法的点），然后再扩展一步，看一开始的点是否能到。（不难想到这样的复杂度是跟走两步一样的）
对于情况二，我们可以先预处理出走到最后的点的时候，中间有多少种走法，中间点权值和是否限购它那个。（其实就是跟情况一的走两步一样，可以一次处理出来）
然后我们就重新跑一次，然后就拿这次跑的路径和之前跑到这个终点的所有路径匹配权值。
（当然，要去掉两次都是走的这个中间点的路径，减一下就好了）
然后我们就能搞出答案啦。
（记得枚举每个出发点结束之后要清空个数啊，权值和啊那些的）
代码
#include<queue>
#include<cstdio>
#include<vector>
#define ll long long
#define mo 1000000007
using namespace std;
int n, m, x, y, du[100001];
vector <int> lnk[100001], son[100001];
queue <int> q;
ll ans, val[100001], nm[100001], a[100001];
int pl[100001];
bool in[100001];
int main() {
// freopen("fz.in", "r", stdin);
// freopen("fz.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
lnk[x].push_back(y); lnk[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < lnk[i].size(); j++)
if (i < lnk[i][j]) {
if (lnk[i].size() >= lnk[lnk[i][j]].size()) {
son[i].push_back(lnk[i][j]); du[lnk[i][j]]++;
}
else son[lnk[i][j]].push_back(i), du[i]++;
}
}
for (int i = 1; i <= n; i++) {
if (!du[i]) q.push(i);
}
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < son[now].size(); i++) {//记录是否能到（情况1要用）
du[son[now][i]]--;
if (!du[son[now][i]]) q.push(son[now][i]);
in[son[now][i]] = 1;
}
for (int i = 0; i < son[now].size(); i++) {//预处理走两步（MIM）
for (int j = 0; j < son[son[now][i]].size(); j++) {
val[son[son[now][i]][j]] += a[son[now][i]];
val[son[son[now][i]][j]] %= mo;
nm[son[son[now][i]][j]]++;
if (nm[son[son[now][i]][j]] == 1)
pl[++pl[0]] = son[son[now][i]][j];
}
}
for (int i = 1; i <= pl[0]; i++) {//情况1
int x = pl[i];
for (int j = 0; j < son[x].size(); j++) {
int y = son[x][j];
if (in[y]) {
ans += (val[x] + (a[now] + a[x] + a[y]) % mo * nm[x]) % mo;
ans %= mo;
}
}
}
for (int i = 0; i < son[now].size(); i++) {//情况2
for (int j = 0; j < son[son[now][i]].size(); j++) {
ans += (val[son[son[now][i]][j]] + (a[son[now][i]] + a[now] + a[son[son[now][i]][j]]) * nm[son[son[now][i]][j]] % mo) % mo;
ans -= (a[now] + a[son[son[now][i]][j]] + 2ll * a[son[now][i]]) % mo;
ans = (ans % mo + mo) % mo;
}
}
for (int i = 0; i < son[now].size(); i++) {//清空
in[son[now][i]] = 0;
for (int j = 0; j < son[son[now][i]].size(); j++) {
val[son[son[now][i]][j]] = nm[son[son[now][i]][j]] = 0;
}
}
pl[0] = 0;
}
printf("%lld", ans);
return 0;
}