title
现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。
每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。
给定路径的 价格总和 是该路径上所有节点的价格之和。
另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
示例 1：
输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。
示例 2：
输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。
提示：
1 <= n <= 50edges.length == n - 10 <= ai, bi <= n - 1edges表示一棵有效的树price.length == nprice[i]是一个偶数1 <= price[i] <= 10001 <= trips.length <= 1000 <= starti, endi <= n - 1
solution
先dfs统计每个点经过多少次。
然后再DP，统计最小成本。
class Graph:
'''
边数组转邻接表
'''
def convert_by_edges(edges=List[List[int]]):
graph = collections.defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
return graph
class Solution:
def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
graph = Graph.convert_by_edges(edges)
root = 0
path = []
res = None
end = None
def dfs_p(u, p):
nonlocal res, path
if u == end:
res = path.copy()
return
for v in graph[u]:
if v != p:
path.append(v)
dfs_p(v, u)
path.pop()
cnt = collections.Counter()
for s, e in trips:
path = []
res = None
end = e
dfs_p(s, -1)
cnt[s] += 1
for p in res:
cnt[p] += 1
for i in range(len(price)):
price[i] *= cnt[i]
import functools
@functools.lru_cache(None)
def f(u, p, choose):
res = 0
if choose:
res += price[u] // 2
for v in graph[u]:
if v != p:
res += f(v, u, False)
else:
res += price[u]
for v in graph[u]:
if v != p:
res += min(f(v, u, True), f(v, u, False))
# print(u, p, choose, res)
return res
ans = min(f(root, -1, True), f(root, -1, False))
return ans