解説

辺の木の実の個数 $c_i$ を重みと呼称します。

概要

次数1の頂点とそれを結ぶ辺を削除する操作を可能な限り繰り返します。
操作後に残ったグラフを縮約し、頂点を黒く塗ります。
削除した頂点と辺を戻すとグラフは木となりますが、黒の頂点でのみ折り返しが可能な場合の重み総和の最大値を木DPで求めればよいです。
計算量は$O(M)$です。

グラフの縮約

橋を外したグラフを二重辺連結成分ごとに縮約し、連結成分に含まれる辺の重み総和を頂点の重みとして割り振ります。また、連結成分内に辺を含むものを黒に、含まなければ白に色分けします。
橋を戻した縮約後の木を考えると、元の問題は以下の問題と等価です:

• 木のウォークであって、黒の頂点でのみ折り返しが可能な場合の頂点と辺の集合の重み総和の最大値を求めよ。

等価な証明として、黒く塗る連結成分内で全辺を通過する、任意の$2$頂点間のS-Gウォークの構築法を示します。

• Sを根としたDFS木を構築し、根と結ばれる非木辺のひとつをAとする
• すべての辺を$1$回以上通過するまで、根 -> 木辺 -> 任意の非木辺 -> 木辺 -> 非木辺A -> 根 を繰り返す
• 根 -> 木辺 -> G と移動する

木DPへの帰着

木の問題は黒の頂点間を縮約することで、以下の問題に帰着できます:

• 頂点と辺に重みがついた根つき木が与えられる。根の頂点は黒か白で塗られており、それ以外の頂点はすべて白である。①②の最大値を求めよ。
  ①木のパスであって、通過した頂点と辺の重み総和の最大値を求めよ。
  ②根が黒ならば、根で$1$回だけ引き返せる場合の、通過した頂点と辺の集合の重み総和の最大値を求めよ。

①は木の直径、②は子への辺と頂点の重み総和top2を求める木DPで解けます。