Complexity of a graph parity-coloring problem
Note for each node $v$, there is a one-to-one mapping between the parity of incident edges in $S$ and that of incident edges in $\bar{S}$. This means we can consider the problem with minimum weight equivalently.

The minimum weight version is named min-cost T-join that is studied in this note, which is an application of min-cost matching. 

The idea is, one can decompose $S$ ($\bar{S}$ in the maximum weight version) into a set of edge-disjoint paths joining black nodes (nodes requiring an odd degree), thus the solution is exactly a min-cost matching of the complete graph induced by black nodes where the cost of edge $(u,v)$ is the length of the shortest path between $u$ and $v$ in the original graph. So this problem can be solved by any algorithm solving min-cost matching.



If the graph is a tree, the solution is much simpler as Yuval Filmus pointed out in the comment. 


  Try solving it on a tree using "dynamic programming" (i.e., recursion). For each subtree, solve the corresponding instances with both colors for the root.


Note for a tree, there is at most one feasible solution. So asking for maximum/minimum weight may be meaningless.