結果

問題 No.1221 木 *= 3
ユーザー anagohirameanagohirame
提出日時 2020-08-27 20:09:07
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 2,282 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 200,040 KB
最終ジャッジ日時 2024-04-27 13:57:34
合計ジャッジ時間 9,332 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
18,208 KB
testcase_01 AC 29 ms
11,136 KB
testcase_02 AC 31 ms
11,264 KB
testcase_03 AC 32 ms
11,264 KB
testcase_04 AC 30 ms
11,136 KB
testcase_05 AC 28 ms
11,136 KB
testcase_06 AC 28 ms
11,136 KB
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 AC 1,696 ms
132,648 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque
def input():
	return sys.stdin.buffer.readline()[:-1]

INF = 10**15
class Dinic:
	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None]*self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for w, cap, _ in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			w, cap, rev = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10**30
		g = self.g
		while self.bfs(s, t):
			self.it = list(map(iter, self.g))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for i in range(n-1):
	u, v = map(int, input().split())
	adj[u-1].append((v-1, n+2+i))
	adj[v-1].append((u-1, n+2+i))

S, T = n, n+1
dnc = Dinic(2*n+1)
score = 0

def dfs(i, p, sgn):
	global dnc, score
	if a[i] > 0:
		score += a[i]
		if sgn:
			dnc.add_edge(S, i, a[i])
		else:
			dnc.add_edge(i, T, a[i])
	elif a[i] < 0:
		if sgn:
			dnc.add_edge(i, T, -a[i])
		else:
			dnc.add_edge(S, i, -a[i])

	for j, e in adj[i]:
		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)

dfs(0, -1, 0)
min_cut = dnc.flow(S, T)
print(score - min_cut)
0