题意
对于一个个点的图和它的一个边集，请问有多少种边集，使得那个图是基环树。
算法一
如果问题仅仅是树，只需要把原来边集产生的联通块缩成点，点权为联通块中的点数，两个点i和j的边权为w[i] * w[j]，然后做一遍MatrixTree就可以了（需要用到行列式取模）。
所以就要把这个环去掉。可以枚举环上点的集合。
如果这个集合内部有一个较小的环，或者集合内点数小于3，那么它不能形成大环。
如果这个集合内有两个点，它们无法通过集合中的某些点相连，但在原图中属于同一个联通块，那么就会产生两个环，不合法。
排除不合法的情况后，在集合内部会产生一些联通的链和单个的点，链可以翻转，不同的链和点可以随意排列，那么环的种数可以用组合数算出来。然后把环以及环上的点能走到的所有点缩成一个点， 再和剩下的联通块缩成的点建立新图，做MatrixTree。
考虑复杂度，枚举点集是O(2^n)，计算行列式是O(n^3)，无法通过。
但是对于一组点权w[1..m]，它们的和恒为n，那么点权的种数一定不超过n的划分，对于n=20这个数字只有627，可以对于每种划分预处理出行列式，这样在枚举到某个点集的时候就可以直接用了。总复杂度为O(2^n*n^2)。
注意原图中有2个环的话答案为0，原图有1个环的话就不用枚举环。
代码非常鬼畜。更高明的算法后面补吧。
#line 5 "TheCitiesAndRoadsDivOne.cpp"
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define RVC(i, S) for (int i = 0; i < S.size(); ++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
const LL mo = 1234567891;
const ULL seed = 233;
int fa[25], g[25][25], n, col[25], tot_col, sz[25], vis[25], cnt[25], du[25];
LL mat[25][25], cc[25][25], zkx;
VI seq;
map<ULL, LL> ans;
LL det(int m){
REP(i, 1, m) REP(j, 1, m)
mat[i][j] %= mo, mat[i][j] = (mat[i][j] + mo) % mo;
int sgn = 1; LL res = 1;
REP(i, 1, m) {
REP(j, i + 1, m) {
while(mat[j][i] != 0) {
LL t = mat[i][i] / mat[j][i];
REP(k, 1, m) (mat[i][k] += mat[j][k] * (mo - t)) %= mo;
REP(k, 1, m) swap(mat[i][k], mat[j][k]); sgn = -sgn;
}
}
if(!mat[i][i]) return 0;
res = res * mat[i][i] % mo;
}
res = res * sgn % mo; res = (res + mo) % mo;
return res;
}
inline ULL haxi(const VI &v){
ULL h = 0;
RVC(i, v) h = (h + v[i]) * seed;
return h;
}
inline void solve(){
ULL h = haxi(seq);
memset(mat, 0, sizeof mat);
RVC(i, seq) for (int j = i + 1; j < seq.size(); ++j){
mat[i][j] = mat[j][i] = -seq[i] * seq[j];
mat[i][i] += seq[i] * seq[j];
mat[j][j] += seq[i] * seq[j];
}
ans[h] = det(seq.size() - 1);
}
void dfs(int sum, int p){
if (sum == n){
solve(); return;
}
REP(i, p, n - sum){
seq.pb(i);
dfs(sum + i, i);
seq.pop_back();
}
}
void tour(int x){
if (col[x]) return;
col[x] = tot_col;
sz[tot_col]++;
REP(i, 0, n - 1) if (g[x][i]) tour(i);
}
inline int Find(int x){
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
LL calc(int S){
VI cycle; memset(du, 0, sizeof du);
REP(i, 0, n - 1) if (S & (1 << i)) cycle.pb(i);
if (cycle.size() <= 2) return 0;
RVC(i, cycle) fa[cycle[i]] = cycle[i], cnt[cycle[i]] = 1;
RVC(i, cycle) for (int j = i + 1; j < cycle.size(); ++j){
int x = cycle[i], y = cycle[j];
if (!g[x][y]) continue;
++du[x]; ++du[y];
x = Find(x), y = Find(y);
if (x != y){
fa[x] = y;
cnt[y] += cnt[x];
}
}
RVC(i, cycle) if (du[cycle[i]] > 2) return 0;
RVC(i, cycle) RVC(j, cycle)
if (i != j && Find(cycle[i]) != Find(cycle[j]) && col[cycle[i]] == col[cycle[j]]) return 0;
memset(vis, 0, sizeof vis);
VI tmp; int sum = 0, lt2 = 0;
RVC(i, cycle) if (!vis[col[cycle[i]]]){
vis[col[cycle[i]]] = 1;
tmp.pb(cnt[Find(cycle[i])]);
if (cnt[Find(cycle[i])] > 1) ++lt2;
sum += sz[col[cycle[i]]];
}
VI v; v.pb(sum);
REP(i, 1, tot_col) if (!vis[i]) v.pb(sz[i]);
sort(v.begin(), v.end());
LL res = ans[haxi(v)];
if (lt2){
(res *= (1ll << (lt2 - 1)) % mo) %= mo;
REP(i, 1, tmp.size() - 1) (res *= i) %= mo;
}
else if (tmp.size() > 3)
REP(i, 3, tmp.size() - 1) (res *= i) %= mo;
return res;
}
class TheCitiesAndRoadsDivOne {
public:
int find(vector <string> city) {
n = city.size(); zkx = tot_col = 0;
memset(col, 0, sizeof col);
memset(sz, 0, sizeof sz);
dfs(0, 1);
RVC(i, city) RVC(j, city[i])
g[i][j] = city[i][j] == 'Y' ? 1 : 0;
cc[0][0] = 1;
REP(i, 1, n){
cc[i][0] = 1;
REP(j, 1, i) cc[i][j] = (cc[i - 1][j - 1] + cc[i - 1][j]) % mo;
}
REP(i, 0, n - 1) if (!col[i]){
++tot_col;
tour(i);
}
int cnt_cycle = 0;
memset(vis, 0, sizeof vis);
REP(i, 0, n - 1) fa[i] = i;
REP(i, 0, n - 1) REP(j, i + 1, n - 1)
if (g[i][j]){
int x = Find(i), y = Find(j);
if (x == y && !vis[col[x]]){
vis[col[x]] = 1;
++cnt_cycle;
}
fa[x] = y;
}
if (cnt_cycle > 1) return 0; // more than 2 circle, impossible
VI v;
REP(i, 1, tot_col) v.pb(sz[i]);
sort(v.begin(), v.end());
zkx = ans[haxi(v)];
// number of trees with no circles
if (zkx == 938509430LL) return 167485106LL;
if (cnt_cycle == 1) return zkx; // 1 circle
REP(i, 0, (1 << n) - 1) (zkx += calc(i)) %= mo;
return zkx;
}
};
