序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
---|
给定 $n$ 个区间,第 $i$ 个区间是 $[l_r,r_i]$。
接着,我们构造一个无向图 $G=(V,E)$,其中点集 $V=\{1,2, \dots, n\}$,边集 $E=\{(u,v)~|~1\leq u,v\leq n, [l_u,r_u]\cap [l_v,r_v] \neq \varnothing\} $ 。
即在图 $G$ 中 $u,v$ 之间有连边,当且仅当 $u,v$ 对应的区间有交。
我们定义一个图 $G$ 的导出子图为满足点集 $V'\subseteq V(V'\neq \varnothing)$,且边集 $E'=\{(u,v)~|~u\in V', v\in V', (u,v)\in E\}$ 的图 $G'=(V',E')$。
即由图 $G$ 顶点的一个非空子集和该图中两端均在该子集的所有边的集合组成的图即为图 $G$ 的导出子图。
求 $G$ 有多少个不同的导出子图 $G'$,使得 $G'$ 是一棵树。答案对 $10^9+7$ 取模。