上次来UOJ看发现UOJ多了俩题，而且好多人都A了一题，于是就准备也来A一题

一眼看起来是个模板题，DAG子图计数，然而并不会= =算了先看测试点吧

【以下是本蒟蒻自己闷声做大死的口胡做法，不保证是正解】

测试点1

$|V|=1000$，$|E|=100000$，好大，想弃疗。

不过既然是第一个点应该是个特殊点。

写了个程序验证，发现

$$\forall (u,v)\in E,u\le v$$

于是答案就是 $2^k$ 的形式，很快就搞出来了。

测试点2

一眼看出特殊图，每个点 $i$ 向 $[i-4,i+4]$ 内的点连边，即

$$\forall (u,v)\in E,|u-v|\le 4$$

也就是从左到右决定每条边选不选的时候，只有最近4个点的连通性影响状态。

状压4个点的传递闭包跑个DP，即设 $f(i,S)$ 为已确定点集 $\{1,2,...,i-1\}$ 内边的状态，且 $\{i-4,...,i-1\}$ 的传递闭包为 $S$，考虑边集 $E_i=\{(u,v)\in E|\begin{cases}u=i,\\v < i \end{cases}\lor\begin{cases}u < i,\\v=i\end{cases}\}$ 选不选，可以得到

$$f(i,S)=\sum_{E'\subseteq E_i}f(i+1,S')$$

其中 $S'$ 为加入边集 $E'$ 后 $\{i-3,...,i\}$ 的传递闭包。

不过感觉似乎做麻烦了……

测试点3

发现还是特殊图，性质是 $|V|=|E|$，且 $\forall v\in V$，$\deg^+(v)=1$。

因此从任意 $v\in V$ 出发都有唯一的无限长的路径（即有环，并且环是唯一的），做法类似某NOIP题。

其实答案形式很像第1个点

测试点4

和测试点2类似的特殊图，每个点 $i$ 向 $[i-7,i+7]$ 内的点连边，即

$$\forall (u,v)\in E,|u-v|\le 7$$

状压7个点的传递闭包跑个DP，唯一和测试点2不同的是数据范围变大了，不过状态不满，用hash表（C++ 可以使用STL中的 map）即可优化。

跑好慢不过总算能跑出来了- -

测试点5

$|V|=100$，$|E|=400$，没啥规律，感觉数据是随机的

每个连通块不大？

写了个Floyd验证了一下，确实每个强连通块边数都很少。

分块暴力枚举边集，最后乘积即可。

这个做法可以过第2个点？（看样子真是做麻烦了）

测试点6

特殊图，通过观察 $|E|=|V|(|V|-1)$ 以及程序验证，发现 $G=(V,E)$ 是一个简单图，且

$$\forall u,v\in V,u\ne v,(u,v)\in E$$

暴力找出前几项查OEIS 这当然不是正确姿势

吓得我赶紧去研究了下主旋律那题怎么做

做过主旋律的人都知道 是个很难想但不难写的递推，$f(i)$ 表示 $i$ 个点的简单DAG数量

递推时枚举源点个数，由于会互相影响所以要容斥原理，即枚举源点个数 $j$，则取 $j$ 个源点有 $C_i^j$ 种，$j$ 个源点间不能有边，且它们到 $i-j$ 个其它点的边可以任选，其它 $i-j$ 个点内不能有环，有

$$f(i)=\sum_{j=1}^i(-1)^{j-1}C_i^j2^{j(i-j)}f(j)$$

不容斥行吗？把源点数记在状态里面可以过这个点，只是复杂度比较差没法扩展到后面点的做法= =

测试点7

$|V|=12$，$|E|=66$，点很少，不过，第5个点的程序废话当然跑不出来

做法和第6个点类似，$f(S)$ 表示点集 $S$ 内是DAG的方案数。

递推时枚举 $T\subseteq S$ 作为源点集合，那么 $T$ 内不能有边，$T$ 到 $S-T$ 可以任选，$S-T$ 内也必须是个DAG，容斥即可，有

$$f(S)=\sum_{T\subseteq S,T\ne\varnothing}(-1)^{|T|-1}2^{g(T,S-T)}f(S-T)$$

其中 $g(S,T)$ 表示满足 $(u,v)\in E,u\in S,v\in T$ 的边 $(u,v)$ 数量。

测试点8

$|V|=20$，$|E|=190$，同测试点7。

唯一不同的是要用一些奇技淫巧把递推优化成均摊 $O(1)$

$g(S,T)$ 不好预处理，于是我对每个 $S\subseteq V$ 和 $v\in V$ 预处理了 $g(S,\{v\})$，递推的时候动态推就行啦。

复杂度 $O(3^{|V|})$ 看起来不到 $1\mathrm{min}$ 就能跑出来

测试点9

$|V|=102$，$|E|=201$，点变多了不会

看了一会儿发现还是个特殊图

每个点 $i$ 关联 $2$ 条边与编号小于 $i$ 的点连接，不过方向不一定，即对每个点 $i$，存在 $j_1\ne j_2$ 使得 $(i,j_1)$ 与 $(j_1,i)$ 至少有一个属于 $E$，$(i,j_2)$ 与 $(j_2,i)$ 至少有一个属于 $E$。

这种情况显然是可以缩边的？

问题：给定图 $G=(V,E)$，每条边 $e\in E$ 有两个权值 $w_0(e)$ 和 $w_1(e)$，求 $G$ 的全部有向无环生成子图 $G'=(V,E')$ 的权值积 $\prod_{e\in E'}w_1(e)\cdot\prod_{e\in E-E'}w_0(e)$ 之和 $F(G)$.

如果 $\deg^-(i)=\deg^+(i)=1$，设 $(x,i)\in E$，$(i,y)\in E$，$w_0(x,i)=w_0(i,y)=w_1(x,i)=w_1(i,y)=1$，考虑生成子图 $G'=(V,E')$ 的两种情况，一种是 $(x,i)\in E'$ 且 $(i,y)\in E'$，此时的和为 $F(G-i+(x,y))$，另一种是 $(x,i)\not\in E'$ 或 $(i,y)\not\in E'$，此时的和为 $3F(G-i)$，因此可以缩掉这条边，即删掉点 $i$，加入边 $(x,y)$，并且令 $w_0(x,y)=3$，$w_1(x,y)=1$，此时的 $F(G)$ 就是答案. 每次找出一个点 $i$ 并且缩掉，就能减小点集.

缩边以后变成带权边，然而缩到 $|V|=23$ 的时候其它点 $i$ 都有 $\deg^-(i)+\deg^+(i)\ge 3$ 了，$23$ 个点显然短时间跑不出来。

通过手工枚举了一下其中两个点的情况，又缩了两个点，这样剩下 $21$ 个点。

剩下的点懒得处理了反正点已经少了很多，那就直接套第7、8个测试点程序跑就OK

for each edge e = (u, v) :
    e->w(0) = e->w(1) = 1
s = 1
for i = n ... 24 :
    取出与 i 关联的两条边 e[0], e[1]，设 e[0], e[1] 关联的另一个点分别为 v[0], v[1]
    if e[0], e[1] 均从 i 连出或均连入 i :
        s *= 4
    else :
        if e[0] 指向 i:
            swap ( v[0], v[1] )
        构造新边 e = ( v[0], v[1] )
        e->w(0) = 3
        e->w(1) = 1
        将 e 加入图中
    将 i, e[0], e[1] 从图中删除

... // 通过类似的操作手工处理去掉 22, 23 这两个点

测试点10

和9有点像，每个点 $i$ 关联 $3$ 条边与编号小于 $i$ 的点连接，不过方向不一定

按照测试点9的想法想下去，发现如果缩边就会出现“一条边与3个点相连”的边。好神奇。

于是研究了一下这种新图的处理方法。

用 $(u,v,w)$ 表示连接三点 $u,v,w\in V$ 的边，一条边可能有多个选取状态，如可以选“$u$ 连到 $v$”“$u,v,w$ 互相可达”等等，对每条边的每种选取状态（可以表示为 $u,v,w$ 三个点的传递闭包） $S$ 赋上权，得到带权图 $G$，边 $e$ 选取状态 $S$ 的权为 $f_S(e)$。

问题：求 $G$ 的所有不会出现环的选取方式 $G'$ 的权值积 $\prod_{e\in E}f_{S_{G'}(e)}(e)$ 之和 $F(G)$，其中 $S_{G'}(e)$ 为在选取方式 $G'$ 下 $e$ 的状态.

如果存在 $i\in V$，使得 $i$ 在 $G$ 中恰与 $3$ 个点 $j_1,j_2,j_3$ 关联（即包含 $i$ 的所有边包含的点集的并集为 $\{i,j_1,j_2,j_3\}$），不妨设有 $k$ 条包含 $i$ 的边 $e_1,e_2,...,e_k$，则对每条边的每一种选择情况 $S_1,S_2,...,S_k$，权值积的和等于从 $G$ 中去掉点 $i$ 及边 $e_1,...,e_k$ 并加入选取状态为 $S'$ 的边 $e'=(j_1,j_2,j_3)$ 后，在选 $e'$ 的条件下的权值积的和乘以 $\prod_{s=1}^kf_{S_s}(e_s)$，其中 $S'$ 为合并 $S_1,...,S_k$ 后 $j_1,j_2,j_3$ 的传递闭包.

因此构造边 $e'=(j_1,j_2,j_3)$，满足 $f_S(e')$ 等于所有满足 $S_1,...,S_k$ 合并后 $j_1,j_2,j_3$ 的传递闭包等于 $S$ 的 $\prod_{s=1}^kf_{S_s}(e_s)$ 之和，那么 $F(G)=F(G-\{i\}-\{e_1,...,e_k\}+e')$.

不过会不会出现缩到后面一个点与 $k(k\ge 4)$ 个点相连？这样就比较麻烦了= =

然后试了下，还好，一直缩到 $|V|=3$ 都没有出现一条边与 $k(k\ge 4)$ 个点相连的情况

于是果断写了个 struct 存每条“与3个点相连的边”每一种传递闭包的权值（实质就是方案数）

缩点的时候做个类似卷积的东西合并方案数

然后发现缩一半被卡住了……什么情况？缩的时候会出现大量重边，需要及时去重

最后剩下3个点

就解决啦

怎么一直过不了check？

有个地方爆数组了……调了我好久好久……

for each e = ( u, v ) :
    将 e 改成边 e = ( u, v, null ), e->f(0) = e->f(1) = 1   // 1表示只连u到v的传递闭包
for i = n ... 4 :
    取出与 i 关联的所有边 E' = { e[0], e[1], ..., e[k-1] }
    取出 i 关联的 3 个点 { v[0], v[1], v[2] }
    构造新边 e' = ( v[0], v[1], v[2] ), 所有的 e'->f(S) = 0
    枚举 e[0] 选择的传递闭包 S[0] :
        枚举 e[1] 选择的传递闭包 S[1] :
            ....
            枚举 e[k-1] 选择的传递闭包 S[k-1] :
                if S[0], S[1], ..., S[k-1] 合并后无环 :
                    合并得到 v[0], v[1], v[2] 的传递闭包 S'
                    e'->f(S') += e[0]->f(S[0]) * e[1]->f(S[1]) * ... * e[k-1]->f(S[k-1])
    将点 i 与 E' 从图中删除
    if 图中存在同样连接 v[0], v[1], v[2] 的边 e :
        构造新边 e'' = ( v[0], v[1], v[2] ), 所有的 e''->f(S) = 0
        枚举 e 选择的传递闭包 S :
            枚举 e' 选择的传递闭包 S' :
                if S, S' 合并后无环 :
                    合并得到 v[0], v[1], v[2] 的传递闭包 S''
                    e''->f(S'') += e->f(S) * e'->f(S')
        e' = e''
        将边 e 从图中删除
    将边 e' 加入图中
取出剩下的边集 E = { e[0], e[1], ..., e[m-1] }
ans = 0
枚举 e[0] 选择的传递闭包 S[0] :
    枚举 e[1] 选择的传递闭包 S[1] :
        ....
        枚举 e[m-1] 选择的传递闭包 S[k-1] :
            if S[0], S[1], ..., S[m-1] 合并后无环 :
                ans += e[0]->f(S[0]) * e[1]->f(S[1]) * ... * e[m-1]->f(S[m-1])
return ans

感觉做这种题像游戏打BOSS一样，越到后面的关越想弃疗

【虽然总算做完了但考场上恐怕只能做50分了……】

另外，做完以后去看myy的题解，最后两个点的正解居然是树分解……myy太强啦%%%树分解这玩意我听都没听说过……果然我太弱啦