結果

問題 No.1221 木 *= 3
ユーザー anagohirame
提出日時 2020-08-28 02:13:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,440 bytes
コンパイル時間 2,900 ms
コンパイル使用メモリ 213,224 KB
最終ジャッジ日時 2025-01-13 15:54:14
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1000000000000000;
const int MAX = 100010;

int n, S, T;
vector<ll> a(MAX), b(MAX);
vector<vector<P>> adj(MAX);
ll score = 0;

struct max_flow {
	struct edge { ll to, cap, rev; };
	ll V;
	vector<vector<edge>> G;
	vector<ll> itr, level;

	max_flow(ll V) : V(V) { G.assign(V,vector<edge>()); }

	void add_edge(ll from, ll to, ll cap) {
		G[from].push_back((edge) {to, cap, (ll) G[to].size()});
		G[to].push_back((edge) {from, 0, (ll) G[from].size()-1});
	}

	void bfs(ll s) {
		level.assign(V,-1);
		queue<ll> q;
		level[s] = 0; q.push(s);
		while (!q.empty()) {
			ll v = q.front(); q.pop();
			for(auto &e: G[v]){
				if (e.cap > 0 and level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}

	ll dfs(ll v, ll t, ll f) {
		if (v == t) return f;
		for (ll& i = itr[v]; i < (ll) G[v].size(); ++i) {
			edge& e = G[v][i];
			if (e.cap > 0 and level[v] < level[e.to]) {
				ll d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	ll run(ll s, ll t) {
		ll ret = 0, f;
		while (bfs(s), level[t] >= 0) {
			itr.assign(V,0);
			while ((f = dfs(s, t, INF)) > 0) ret += f;
		}
		return ret;
	}
};

max_flow dnc(2*MAX+10);

void dfs(int i, int p, int sgn) {
	if (a[i] > 0) {
		score += a[i];
		if (sgn) dnc.add_edge(S, i, a[i]);
		else dnc.add_edge(i, T, a[i]);
	}
	else if (a[i] < 0) {
		if (sgn) dnc.add_edge(i, T, -a[i]);
		else dnc.add_edge(S, i, -a[i]);
	}
	for (P pp : adj[i]) {
		int j = pp.first; int e = pp.second;
		if (j == p) continue;
		if (b[i]+b[j] >= 0) {
			score += b[i]+b[j];
			if (sgn) {
				dnc.add_edge(i, e, INF);
				dnc.add_edge(j, e, INF);
				dnc.add_edge(e, T, b[i]+b[j]);
			}
			else {
				dnc.add_edge(e, i, INF);
				dnc.add_edge(e, j, INF);
				dnc.add_edge(S, e, b[i]+b[j]);
			}
			dfs(j, i, sgn);
		}
		else {
			if (sgn) dnc.add_edge(j, i, -b[i]-b[j]);
			else dnc.add_edge(i, j, -b[i]-b[j]);
			dfs(j, i, 1^sgn);
		}
	}
	return;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) cin >> b[i];
	for (int i = 0; i < n-1; ++i) {
		int u, v; cin >> u >> v;
		adj[u-1].push_back(make_pair(v-1, n+2+i));
		adj[v-1].push_back(make_pair(u-1, n+2+i));
	}

	S = n; T = n+1;
	dfs(0, -1, 0);
	cout << score - dnc.run(S, T) << endl;
	return 0;
}
0