好题要点赞！作为元芳厨，能推出来这个题觉得非常开心 >w<！

0x01 题意观察

比较关键的条件是好找的：一、Bessie 不走回头路；二、图中一条边属于 不超过一个环，即图是一个可爱的 仙人掌。$n \le 10^{4}$ 给的信息目前不多，只能推出复杂度上界 $\mathcal{O}(n^{2})$；$m \le \dfrac{3 (n - 1)}{2}$ 应该是仙人掌带来的性质，没啥用。

0x02 思路分析

这么一看条件还挺简洁。由于一般图 有环 是不好处理概率问题的，不难想到最后要建出 狭义元芳树 刻画问题。（诶是狭义吧，元芳树毕竟起源于仙人掌，广义元芳树是用于点双的吧……）但当务之急是找到 有关于概率计算 的性质，元芳树等下再管 qwq。（upd：如果推导过程有发现比较奇怪的地方，可以看 0x04 部分给出的两种元芳树定义……）

看一眼部分分，给的有点少，树的部分直接搜一边路径就没了，所以直接考虑 环 的处理。这个时候可以像我一样画几张图然后手算 4 整整版的路径概率然后发现啥规律也没有。 其实是有微弱发现的：正着走和反着走环，到环上点的概率不同，但 走完的概率相同，又因为入环点有两条路走各带 $\dfrac{1}{2}$ 的概率，合起来就是环上每个点继续走环的概率乘积。

确实很微（mei）弱（yong），所以只能从 暴力推式子 的角度考虑了。放到元芳树上考虑游走，首先点 $x$ 的答案可以直接看作 $1 \rightsquigarrow x$ 的概率乘上停在 $x$ 的概率，于是只用关心 走各种边的概率 以及回到某个点的 状态和概率，因为能不能继续走会影响当前停不停的概率（不能走就成 $1$ 了）。接着对于一个 元点，游走过程形如 走若干芳点后 在任意子树内节点结束，或者本身在环里的话 走环的下一步；而 芳点 只能走完元点回去或者子树内结束。复杂之处在哪里呢？元点，因为 走先导环 会影响接下来选边的概率，于是对其重点讨论。

0x03 式子推导

思考哪些信息对元点的决策有影响。发现不论是走儿子元点还是走当前环的下一步，其结果都是 不再回来，说明这些决策的概率是 没有后效性且相等的。考虑一起计算，设 $q_{x} \ (x \le n)$ 为元点 $x$ 走完若干芳点后走这种 不归路 的概率；又发现走芳点也有可能在芳点内部结束游走，需要知道走完芳点的概率，也设为 $q_{x} \ (x > n)$，为作区分下面记为 $q'_{x}$。

发现这俩玩意儿存在 互相依赖 的关系，但都是树上父子关系的依赖，并不影响。$q'$ 实际上是好算的，$q'_{x} = \prod_{y \in \text{son}(x)} q_{y}$；$q$ 则需要一点点推导，考虑先导环组合对 $q$ 的概率影响，有式子：

$$q_{x} = \sum_{S \subseteq \text{sonFang}(x)} (\prod_{i \in S} q'_{i}) \times (\prod_{i = 1}^{\lvert S \rvert} (1 - p_{x}) \cdot \frac{2 (\lvert S \rvert - i + 1)}{a + 2 (b - i + 1)}) \times (1 - p_{x}) \cdot \frac{1}{a + 2 (b - \lvert S \rvert)}$$

意义是走完所有环的概率，乘上每一步不在 $x$ 结束且选中 $S$ 中环的概率（注意 $q'_{x}$ 只算了 走完 的概率！），再乘上选中任意出边的概率。然而看着非常不可以做，注意到与 $S$ 实际值 有关的只有 $\prod q'$ 项，考虑枚举 $\lvert S \rvert$：

$$q_{x} = \sum_{i = 0}^{b} (\prod_{j = 1}^{i} \frac{2 (i - j + 1)}{a + 2 (b - j + 1)}) \times (1 - p_{x}) \cdot \frac{1}{a + 2 (b - i)} \times \sum_{S \subseteq \text{sonFang}(x), \lvert S \rvert = i} \prod_{j \in S} (1 - p_{x}) \cdot q'_{j}$$

诶这个时候我们发现后面一块是可以 $\mathcal{O}(n^{2})$ 背包的！（$1 - p_{x}$ 扔到后面是不想预处理幂次放背包里处理。）那么我们就只用关心前面了，设其为 $\text{calc}(a, b, i)$，我们需要让 $\text{calc}$ 是个 $\mathcal{O}(1)$ 的函数，于是大力拆式子（甚至是第一次写 $\LaTeX$ 的除号）：

$$\begin{aligned} \text{calc}(a, b, i) &= \prod_{j = 1}^{i} \frac{2 (i - j + 1)}{a + 2 (b - j + 1)} \\ &= \prod_{j = 0}^{i - 1} 2 (i - j) \div \prod_{j = 0}^{i - 1} a + 2 (b - j) \\ &= 2^{i} \times i! \div \begin{cases} 2^{i} \times (\frac{a + 2 b}{2})! \div (\frac{a + 2 b - 2 i}{2})! & 2 \mid x \\ (x + 2 y + 1)! \div (x + 2 y - 2i - 1)! \div (2^{i} \times (\frac{a + 2 b + 1}{2})! \div (\frac{a + 2 b - 2 i - 1}{2})!) & 2 \nmid x \end{cases} \\ &= \begin{cases} i! \div (\frac{a + 2 b}{2})^{\underline{i}} & 2 \mid x \\ 2^{2 i} \times i! \div ((x + 2 y + 1)^{\underline{i}} \div (\frac{x + 2 y + 1}{2})^{\underline{i}}) & 2 \nmid x \end{cases} \end{aligned}$$

非常恐怖，不知道哪来的耐心推了三遍的，大概是厨力罢。不过感谢

/item/%E5%8F%8C%E9%98%B6%E4%B9%98/9500461) 是可以预处理的，不用阶乘暴力推，大家不要学鼠（

总之 $\text{calc}$ 做到 $\mathcal{O}(1)$ 了，求 $q_{x}$ 的复杂度也可以接受力。整理一下，我们现在知道了走环的成功率、元点走不归路的概率，差了啥？走芳点的概率以及走到环上某个点的概率。

后者是好处理的，既然我们已经求出环上每个元点走向 不归路 的方案，那只要模拟一下按顺序乘概率就好了。思考前者，我们发现走点（或者说走边）的决策过程都是相似的，可以依照先前求 $q$ 的思路，枚举先导环算走入的概率。唯一的问题是，走的先导环不能包括自己，咋搞捏？这个简单，由于我们之前的背包 不是判定性背包，而是类似 计数背包 的形式，我们可以对于每个芳点 $\mathcal{O}(n)$ 做 撤销背包，由于搜索总 $\mathcal{O}(n)$ 不是瓶颈，总复杂度依旧 $\mathcal{O}(n^{2})$ 轻松通过。

于是这个章节就撒花了！但你先别急，还有代码，如果愿意且听我有点菜的实现……

0x04 小小细节

现在可以考虑元芳树了。相比于大部分人先学的广义元芳树，仙人掌上的狭义元芳树有这么一个特点：存在两个直接相连的元点。

上（博客中为数不多）图就是一个示例。狭义元芳树路径不是元芳点交替的原因在于，其只将 一个环 当作一个整体，而不是 一个点双连通分量。这限制了其对一般图的处理，却有一个有点：更为 完整地 保留了环的信息（相对点双），同时减少了特殊图上的分讨问题。所以广义元芳树在这题是可以做的，只不过细节更多。

于是相对应的，改一下 tarjan 建元芳树的代码：

/* declaration */
int dfn[N], low[N], cnt, tot;    // 时间戳，总点数
std::vector<std::pair<int, int>> G[M][2];
// 元芳树用 vector 存，pair<int, int> 相当于把走边的概率记为边权了方便处理
static std::stack<int> s;        // 定义在 tarjan 里记录路径的栈

/* kernel */
if (!dfn[y]) {
   tarjan(y, x);

   if (low[y] > dfn[x]) {
      // 最小后继大于时间戳，说明 DFS 生成树子树中没有连向祖先的边
      // 人话就是可以直接连
      G[x][0].emplace_back(y, 0);
      G[y][0].emplace_back(x, 0);

      s.pop();
   } else if (low[y] == dfn[x]) {
      // 刚好成环，x 是环开始的地方，于是取出环上的点连虚点
      // 注意到 stack 中的存点顺序是搜索序，我们取出来的点实际上保存了环的相对顺序
      G[++tot][0].clear(), G[tot][1].clear();

      while (s.top() ^ y) {
         int k = s.top();
         s.pop();

         G[tot][0].emplace_back(k, 0);
         G[k][1].emplace_back(tot, 0);
      }

      s.pop();

      G[tot][0].emplace_back(y, 0);
      G[tot][0].emplace_back(x, 0);

      G[y][1].emplace_back(tot, 0);
      G[x][1].emplace_back(tot, 0);
   } else
      chkMn(low[x], low[y]);
} else
   chkMn(low[x], dfn[y]);

随后是处理 $q_{x}$ 等信息。有没有发现前面漏讲了 停在某个点的概率 怎么求，这是跟 $q_{x}$ 差不多的，只不过要考虑剩下出边的数量，于是俩小只放一起求，这也就是为啥上面推式子时给 $\text{calc}$ 函数求的东西留了一手。同样为了方便起见，吾将元芳点分别封装成一个 DFS 函数：

/* kernel */

int q[M], res[N];
// q：元点是不归路概率，芳点是走完环概率；res：停住的概率
void DFS_Yuan(int, int), DFS_Fang(int, int);
// 注意到两个 DFS 互相嵌套，事先声明
int calc(int x, int y, int i) {  // 这个实现随意了 qwq
   int t = x + y * 2 + (x & 1);

   if (x & 1)
      return mod(mod(1ll * fac[i] * pw[i * 2]) *
                 mod(1ll * fallInv(t, 2 * i) * fallFac(t / 2, i)));
   else
      return mod(1ll * fac[i] * fallInv(t / 2, i));
}

void DFS_Yuan(int x, int fa) {
   auto &G0 = G[x][0], &G1 = G[x][1];

   if (fa > n)                                     // 提前删父亲
      G1.erase(std::find(G1.begin(), G1.end(), std::make_pair(fa, 0)));
   else if (fa)
      G0.erase(std::find(G0.begin(), G0.end(), std::make_pair(fa, 0)));

   // a, b 分别是不归路数量和芳点数量，dp 就是背包数组
   int a = G0.size() + (fa > n), b = G1.size(), t = sub(1, p[x]);
   std::vector<int> dp(b + 1);

   dp[0] = 1;
   for (auto [y, z] : G1) {
      DFS_Fang(y, x);                              // 先处理芳点，算元点概率需要

      int k = mod(1ll * t * q[y]);                 // 算上 x 点不停的概率

      for (int i = b; i; --i) pls(dp[i], mod(1ll * dp[i - 1] * k));
   }

   q[x] = res[x] = 0;
   for (int i = 0; i <= b; ++i) {
      pls(q[x], mod(mod(1ll * calc(a, b, i) * dp[i]) *
                    mod(1ll * t * inv[a + b * 2 - i * 2])));

      pls(res[x], mod(mod(1ll * calc(a, b, i) * dp[i]) *
                      (a + b - i ? p[x] : 1)));    // 判掉剩余出边
   }

   for (auto &[y, z] : G1) {
      int k = mod(1ll * t * q[y]);

      // 撤销背包，计算走芳点的概率
      for (int i = 1; i <= b; ++i) dec(dp[i], mod(1ll * dp[i - 1] * k));

      for (int i = 0; i < b; ++i)
         pls(z, mod(mod(1ll * calc(a + 2, b - 1, i) * dp[i]) *
      mod(2ll * t * inv[a + b * 2 - i * 2])));

      for (int i = b; i; --i) pls(dp[i], mod(1ll * dp[i - 1] * k));
   }

   for (auto &[y, z] : G0) {
      z = q[x];

      DFS_Yuan(y, x);
   }
}
void DFS_Fang(int x, int fa) {
   auto &G = ::G[x][0];

   G.erase(std::find(G.begin(), G.end(), std::make_pair(fa, 0)));

   int t = INV_2;

   for (auto &[y, z] : G) {
      DFS_Yuan(y, x);

      pls(z, t), mul(t, q[y]);      // 前后缀就没啥技术含量了
   }

   t = INV_2;
   for (int i = G.size() - 1; ~i; --i) {
      auto &[y, z] = G[i];

      pls(z, t), mul(t, q[y]);

      if (!i) q[x] = add(t, t);     // 注意一下初始概率是 0.5
   }
}

诶怎么写的时候感觉那么困难勒，鉴定为菜导致的。

0x05 纯享代码

7.5 KB 其实不那么纯享。是不是应该放剪切板（鼠鼠异或 /yiw）……

/* 年挽红枫，溪傍芦荻。*/

#ifdef DEBUG
#include <iostream>
#include <cmath>
#include <ctime>

bool Mbe;
void _Dihan();
#endif

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>

typedef long long i64;
typedef unsigned long long ull;
typedef double f32;
typedef long double ldb;
typedef __int128 i28;
typedef unsigned uit;

template <typename T>
inline bool chkMx(T &x, T y) { return x < y ? x = y, true : false; }
template <typename T>
inline bool chkMn(T &x, T y) { return x > y ? x = y, true : false; }

namespace IO {

#define file(s) freopen(#s".in", "r", stdin), freopen(#s".out", "w", stdout)

constexpr int SIZE = 1 << 21;

char ibuf[SIZE], *p1 = ibuf, *p2 = ibuf, obuf[SIZE], *p3 = obuf;

#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define gc()                                                               \
   (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
#define pc(ch) (p3 == obuf + SIZE && flush(), *p3++ = ch)

class Flush { public: ~Flush() { flush(); } } _;

template <typename T>
inline void read(T &x) {
   static char c;
   static int f;

   x = f = 0;
   while (!isdigit(c = gc())) f |= c == '-';

   while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
   f && (x = -x);
}
template <typename T>
inline T read() {
   static T x;

   return read(x), x;
}

template <typename T>
inline void write(T x) {
   static char s[50];
   static int t;

   x < 0 && (pc('-'), x = -x);
   do s[++t] = x % 10 ^ 48; while (x /= 10);

   while (t) pc(s[t--]);
}
inline void write(char c) { pc(c); }
template <typename T>
inline void write(T *s) { while (*s) pc(*s++); }

template <typename ...Args>
inline void read(Args &...args) { (read(args), ...); }
template <typename ...Args>
inline void write(Args ...args) { (write(args), ...); }

}  // namespace IO
using namespace IO;

constexpr int N = 1e4 + 5;
constexpr int M = 1.5e4 + 5;

namespace Math {

constexpr int P = 1e9 + 7;
constexpr int INV_2 = 5e8 + 4;

#define mod(x) ((x) % P)

inline int &pls(int &x, int y) { return (x += y) < P || (x -= P), x; }
inline int &dec(int &x, int y) { return (x -= y) < 0 && (x += P), x; }
inline int &mul(int &x, int y) { return x = mod(1ll * x * y); }

inline int add(int x, int y) { return pls(x, y); }
inline int sub(int x, int y) { return dec(x, y); }

inline int quickPow(int a, int x = P - 2, int ret = 1) {
   for (; x; x >>= 1, mul(a, a)) x & 1 && mul(ret, a);

   return ret;
}

int fac[N], iFac[N];
void initFac() {
   fac[0] = 1;
   for (int i = 1; i < N; ++i) fac[i] = mod(1ll * fac[i - 1] * i);

   iFac[N - 1] = quickPow(fac[N - 1]);
   for (int i = N - 1; i; --i) iFac[i - 1] = mod(1ll * iFac[i] * i);
}
int fallFac(int a, int x) {
   if (a - x <= 0) return fac[a];

   return mod(1ll * fac[a] * iFac[a - x]);
}
int fallInv(int a, int x) {
   if (a - x <= 0) return iFac[a];

   return mod(1ll * iFac[a] * fac[a - x]);
}

int inv[N];
void initInv() {
   inv[1] = 1;
   for (int i = 2; i < N; ++i) inv[i] = sub(0, mod(1ll * P / i * inv[P % i]));
}

int pw[N];
void initPw() {
   pw[0] = 1;
   for (int i = 1; i < N; ++i) pw[i] = add(pw[i - 1], pw[i - 1]);
}

class Init { public: Init() { initFac(), initInv(), initPw(); } } $;

}  // namespace Math
using namespace Math;

int n, m, p[N];
struct Edge {
   int t, nx;
} eg[M << 1];
int nm, hd[N];
void addEdge(int f, int t) {
   eg[++nm] = {t, hd[f]};
   hd[f] = nm;
}

int dfn[N], low[N], cnt, tot;
std::vector<std::pair<int, int>> G[M][2];
void tarjan(int x, int fa) {
   static std::stack<int> s;

   dfn[x] = low[x] = ++cnt, s.emplace(x);
   G[x][0].clear(), G[x][1].clear();

   for (int i = hd[x]; i; i = eg[i].nx) {
      int y = eg[i].t;
      if (y == fa) continue;

      if (!dfn[y]) {
         tarjan(y, x);

         if (low[y] > dfn[x]) {
            G[x][0].emplace_back(y, 0);
            G[y][0].emplace_back(x, 0);

            s.pop();
         } else if (low[y] == dfn[x]) {
            G[++tot][0].clear(), G[tot][1].clear();

            while (s.top() ^ y) {
               int k = s.top();
               s.pop();

               G[tot][0].emplace_back(k, 0);
               G[k][1].emplace_back(tot, 0);
            }

            s.pop();

            G[tot][0].emplace_back(y, 0);
            G[tot][0].emplace_back(x, 0);

            G[y][1].emplace_back(tot, 0);
            G[x][1].emplace_back(tot, 0);
         } else
            chkMn(low[x], low[y]);
      } else
         chkMn(low[x], dfn[y]);
   }
}

int q[M], res[N];
void DFS_Yuan(int, int), DFS_Fang(int, int);
int calc(int x, int y, int i) {
   int t = x + y * 2 + (x & 1);

   if (x & 1)
      return mod(mod(1ll * fac[i] * pw[i * 2]) *
                 mod(1ll * fallInv(t, 2 * i) * fallFac(t / 2, i)));
   else
      return mod(1ll * fac[i] * fallInv(t / 2, i));
}

void DFS_Yuan(int x, int fa) {
   auto &G0 = G[x][0], &G1 = G[x][1];

   if (fa > n)
      G1.erase(std::find(G1.begin(), G1.end(), std::make_pair(fa, 0)));
   else if (fa)
      G0.erase(std::find(G0.begin(), G0.end(), std::make_pair(fa, 0)));

   int a = G0.size() + (fa > n), b = G1.size(), t = sub(1, p[x]);
   std::vector<int> dp(b + 1);

   dp[0] = 1;
   for (auto [y, z] : G1) {
      DFS_Fang(y, x);

      int k = mod(1ll * t * q[y]);

      for (int i = b; i; --i) pls(dp[i], mod(1ll * dp[i - 1] * k));
   }

   q[x] = res[x] = 0;
   for (int i = 0; i <= b; ++i) {
      pls(q[x], mod(mod(1ll * calc(a, b, i) * dp[i]) *
                    mod(1ll * t * inv[a + b * 2 - i * 2])));

      pls(res[x], mod(mod(1ll * calc(a, b, i) * dp[i]) *
                      (a + b - i ? p[x] : 1)));
   }

   for (auto &[y, z] : G1) {
      int k = mod(1ll * t * q[y]);

      for (int i = 1; i <= b; ++i) dec(dp[i], mod(1ll * dp[i - 1] * k));

      for (int i = 0; i < b; ++i)
         pls(z, mod(mod(1ll * calc(a + 2, b - 1, i) * dp[i]) *
                    mod(2ll * t * inv[a + b * 2 - i * 2])));

      for (int i = b; i; --i) pls(dp[i], mod(1ll * dp[i - 1] * k));
   }

   for (auto &[y, z] : G0) {
      z = q[x];

      DFS_Yuan(y, x);
   }
}
void DFS_Fang(int x, int fa) {
   auto &G = ::G[x][0];

   G.erase(std::find(G.begin(), G.end(), std::make_pair(fa, 0)));

   int t = INV_2;

   for (auto &[y, z] : G) {
      DFS_Yuan(y, x);

      pls(z, t), mul(t, q[y]);
   }

   t = INV_2;
   for (int i = G.size() - 1; ~i; --i) {
      auto &[y, z] = G[i];

      pls(z, t), mul(t, q[y]);

      if (!i) q[x] = add(t, t);
   }
}

void getResult(int x, int cur) {
   if (x <= n) mul(res[x], cur);

   for (int i : {0, 1}) for (auto [y, z] : G[x][i])
      getResult(y, mod(1ll * z * cur));
}

void work() {
   read(n, m);
   for (int i = 1; i <= n; ++i) read(p[i]);

   nm = 0, memset(hd + 1, 0, n * sizeof(int));
   for (int i = 1, x, y; i <= m; ++i)
      read(x, y), addEdge(x, y), addEdge(y, x);

   cnt = 0, memset(dfn + 1, 0, n * sizeof(int)), tot = n;
   tarjan(1, 0);
   
   DFS_Yuan(1, 0), getResult(1, 1);

   for (int i = 1; i <= n; ++i) write(res[i], " \n"[i == n]);
}

int main() {
#ifdef DEBUG
   file(cur);
#endif

   for (int _T = read<int>(); _T; --_T) work();

#ifdef DEBUG
   _Dihan();
#endif
   return 0;
}

#ifdef DEBUG
bool Med;
void _Dihan() {
   std::cerr << "Memory: " << abs(&Med - &Mbe) / 1048576.0 << " MB\n";
   std::cerr << "Time: " << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
}
#endif

0x3f 总结后话

发现不看题解写出来题其实是一种享受，没必要纯粹为了量而刷题。题目的中心思想就是 用较为简单的模型刻画复杂的过程。在写代码的过程中还是有多次停下来重构，反映出在纸上推导的能力仍不足，虽然分讨也有点小烦就是啦。应该是改码风后的第一篇题解，实际上在总结反思题目方面还有很大的进步空间，需要努力。

感谢您的垂阅，有错误/不足之处欢迎指出 owo！