結果

問題 No.1221 木 *= 3
ユーザー anagohirameanagohirame
提出日時 2020-08-28 02:13:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,440 bytes
コンパイル時間 3,006 ms
コンパイル使用メモリ 222,872 KB
実行使用メモリ 83,108 KB
最終ジャッジ日時 2024-11-15 16:19:14
合計ジャッジ時間 12,511 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
20,480 KB
testcase_01 AC 12 ms
14,976 KB
testcase_02 AC 9 ms
13,476 KB
testcase_03 AC 12 ms
15,104 KB
testcase_04 AC 9 ms
13,440 KB
testcase_05 AC 11 ms
15,088 KB
testcase_06 AC 10 ms
15,084 KB
testcase_07 TLE -
testcase_08 AC 312 ms
58,204 KB
testcase_09 AC 495 ms
51,700 KB
testcase_10 AC 449 ms
51,248 KB
testcase_11 AC 466 ms
51,548 KB
testcase_12 AC 232 ms
30,776 KB
testcase_13 AC 284 ms
43,892 KB
testcase_14 AC 310 ms
39,044 KB
testcase_15 AC 316 ms
40,208 KB
testcase_16 AC 254 ms
31,668 KB
testcase_17 AC 360 ms
31,336 KB
testcase_18 AC 358 ms
45,172 KB
testcase_19 AC 497 ms
38,424 KB
testcase_20 AC 515 ms
38,420 KB
testcase_21 AC 517 ms
83,108 KB
権限があれば一括ダウンロードができます

ソースコード

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