再谈三(四)元环计数

之前不是很懂我们现在再来了解一下。

三元环

首先考虑我们暴力就是枚举一个点之后枚举边看一下是否相连。

那么我们可以考虑枚举一条边 $(u, v)$ 再枚举 $v$ 的出边看一下是否能连接到 $u$，我们只要预先对于 $u$ 的出边打标记就可以了，复杂度是 $O(m ^ 2)$ 的。

但是事实上，三元环是没有方向的，甚至于对于三元环 $(a, b, c)$ 其任意的排列都是同一个三元环。

所以我们考虑对于边能否进行定向，考虑进行根号分治，让每个点的度数尽量小。所以我们让出边少的连接到出边多的点上。

我们还是枚举点，最外层的循环就是 $O(m)$，考虑如果当前的点度数为 $d$，其出边肯定是到比 $d$ 大的点上，最多是 $\frac{m}{d}$ 。

对于度数 $< \sqrt m$ 的点，其出边可以到达 $O(\sqrt m)$ 最多有 $O(m)$ 个。
对于度数 $> \sqrt m$ 的点，其点的个数总共只有 $\sqrt m$ 个。

所以综上复杂度是 $O(m \sqrt m)$。

for(int i = 1; i <= m; ++ i) r1(eu[i], ev[i]), ++ deg[eu[i]], ++ deg[ev[i]];

auto cmp = [&](int a,int b) -> int {
	return deg[a] > deg[b] || (deg[a] == deg[b] && a < b);
};

for(int i = 1; i <= m; ++ i) {
    if(cmp(eu[i], ev[i])) add(eu[i], ev[i]);
    else add(ev[i], eu[i]);
}

for(int i = 1; i <= n; ++ i) {
    for(int v : vc[i]) vis[v] = i;
    for(int v : vc[i]) for(int k : vc[v]) 
        ans += (vis[k] == i);
}

四元环

考虑还是对于 $\tt DAG$ 进行定向，注意到不能直接使用两个三元环进行拼接。

因为四元组经过某些置换是会成为另外一个四元环，所以这样计算会算少了。

这样也就是意味着我们不能随心所欲改边的方向了，我们考虑之前暴力为什么会慢，主要还是因为一个点被计算的次数太多了，我们是通过限制点度数的情况进行优化。那么我们同样来考虑限制度数的限制。

我们考虑按照度数从大到小排序，设 $rk_i$ 表示 $i$ 的排名，不妨假设从小到大排序。

还是考虑对于四元环 $(a, b, c, d)$ 分成两部分计算 $a \to b \to c, a \to d \to c$，我们钦定答案只能在度数最大的点进行计算即可，每次给点 $c$ 打上来自父亲节点的标记。

考虑如下程序：

for(int i = 1; i <= n; ++ i) {
    for(int j : vc[i]) if(rk[j] < rk[i])
        for(int k : vc[j]) if(rk[k] < rk[i])
            ans += c[k], ++ c[k];
    for(int j : vc[i]) if(rk[j] < rk[i])
        for(int k : vc[j]) if(rk[k] < rk[i])
            -- c[k];
}