SRM 633 Div1 Medium DoubleTree

まず根を 1 つ固定して考える。すると、頂点 x を用いるならば、x の親の頂点 y を用いるという制約がある上でできるだけスコアが大きくなるように頂点集合を選ぶ問題になる。
これは典型最小カット問題 (燃やす埋める問題) なので、最大フローを計算することで答えが求まる。

根を固定することがポイントで、根を固定しないでグラフを構成しようとすると、頂点 x と 頂点 y を用いるならば、その間の頂点を用いるという制約になり、これは最小カットに帰着することができない。

#define N 55
vector<int> g1[N], g2[N], sc;
bool used[N];
int n, s, t;

class DoubleTree {
public:
	void dfs(int u, vector<int> g[N]){
		used[u] = true;
		for(auto &&v: g[u]){
			if(used[v]) continue;
			add_edge(v, u, INF);
			dfs(v, g);
		}
	}
	ll solve(int r){
		rep(i, V) G[i].clear();
		ll sum = 0;
		rep(i, n){
			if(sc[i]<0) add_edge(i, t, -sc[i]);
			else add_edge(s, i, sc[i]), sum += sc[i];
		}
		mset(used, 0);
		dfs(r, g1);
		mset(used, 0);
		dfs(r, g2);
		return sum-max_flow(s, t);
	}
	int maximalScore( vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> sc_) {
		sc=sc_;
		n = sc.size();
		rep(i, n-1){
			g1[a[i]].pb(b[i]);
			g1[b[i]].pb(a[i]);
			g2[c[i]].pb(d[i]);
			g2[d[i]].pb(c[i]);
		}
		s = n; t = s+1;
		ll res = 0;
		rep(i, n) chmax(res, solve(i));
		return res;
	}
};