解説

この問題は、$N$頂点$M$辺の重み付き単純連結無向グラフが与えられたときに、その部分グラフであってかつオイラーグラフであるようなものの辺の重みの合計を最大化する問題です。
ただし、元のグラフには( $1 → 2 \cdots → N → 1$ )というすべての点を含むサイクルが存在し、また部分グラフとしてそのサイクルを含むような部分グラフについてのみ考えればよいとされてます。

ここで、あるグラフがオイラーグラフである( $=$ 一筆書きできる)条件は、

1. グラフが連結である
2. すべての頂点の次数が偶数である

ことです。

ここで、全ての頂点を含むサイクルを含むグラフについてのみ考えればよかったので、 $1$ は自動的に満たされます。
よって、 $2$ についてのみ考えればよいです。
$2$について考えると、あるグラフが条件を満たすグラフかを知るのに必要なのは各頂点の次数の偶奇のみであることがわかります。全ての点についての次数の組み合わせを状態として考えると、ありうる状態は $2^N$ 個です。

ここで、全ての頂点の次数の組を添え字にもつbitDPでこの問題を解くことを考えます。
必ず通らなくてはいけないサイクル以外の辺について、

$dp \lbrack i \rbrack \lbrack state \rbrack =$ $i$ 番目の辺まで見て、 状態が $state$ であるときの重みの総和の最大値

と定義します。

このdpテーブルを更新していくことを考えます。
各辺$i$について、その辺をグラフに追加するかしないかを考えると、追加する場合は辺の両端の頂点の次数の偶奇が変化し、しない場合は状態に変化はありません。
$2^N$通りのすべての状態についてこの遷移を行うことで、dpテーブルを更新することができます。
初期状態は$dp \lbrack 0 \rbrack \lbrack 0 \rbrack = 0$、
M本の辺全てについて遷移が終了した後の $dp \lbrack M \rbrack \lbrack 0 \rbrack$ が答えです。

一つの辺について遷移を行うのにかかる時間は $O(2^N)$ で、 これを $M$ 本の辺すべてについて行うので、計算量 $O(2^N・M)$ でこの問題を解くことができます。