Помогите, пожалуйста, pyhton/c++/c#
Структура королевства — дерево, т.е. королевство состоит из n городов, которые соединены n − 1 дорогами, так, что от любого города можно попасть в любой другой город. Каждый город i обязан отдавать королевству налог, который описывается целым числом p i . В течение следующих q дней проходит одно из следующих событий (пусть сейчас день s ): 1 . Агентство пополнения казны идет по пути от города a s до города b s , и в каждом городе повышает налог до c s , если он меньше c s (формально, пусть путь от a s до b s = { m 1 = a s , m 2 , . . . , m k = b s } ; тогда для любого 1 ≤ i ≤ k агентство пополнения казны делает p m i = max ( p m i , c s ). 2 . Агентство улучшения условий бизнеса идет по пути от города a s до города b s , и в каждом городе понижает налог до c s , если он больше c s (формально, пусть путь от a s до b s = { m 1 = a s , m 2 , . . . , m k = b s } ; тогда для любого 1 ≤ i ≤ k агентство пополнения казны делает p m i = min ( p m i , c s ). 3 . Король хочет узнать, какая сумма налогов на пути от a s до b s . Пожалуйста, помогите ответить на все запросы.
class TreeNode:
def __init__(self):
self.children = []
self.tax = 0
class Kingdom:
def __init__(self, n, taxes):
self.n = n
self.nodes = [TreeNode() for _ in range(n)]
for i in range(n):
self.nodes[i].tax = taxes[i]
self.parent = [-1] * n
self.depth = [0] * n
self.lca_table = []
def add_edge(self, u, v):
self.nodes[u].children.append(v)
self.nodes[v].children.append(u)
def dfs(self, node, par, dep):
self.parent[node] = par
self.depth[node] = dep
for child in self.nodes[node].children:
if child != par:
self.dfs(child, node, dep + 1)
def prepare_lca(self):
max_depth = max(self.depth)
self.lca_table = [[-1] * (max_depth + 1) for _ in range(self.n)]
for i in range(self.n):
self.lca_table[i][0] = self.parent[i]
j = 1
while (1 << j) <= self.n:
for i in range(self.n):
if self.lca_table[i][j - 1] != -1:
self.lca_table[i][j] = self.lca_table[self.lca_table[i][j - 1]][j - 1]
j += 1
def lca(self, u, v):
if self.depth[u] < self.depth[v]:
u, v = v, u
# Bring u and v to the same depth
diff = self.depth[u] - self.depth[v]
for i in range(len(self.lca_table[0])):
if (diff >> i) & 1:
u = self.lca_table[u][i]
if u == v:
return u
for i in reversed(range(len(self.lca_table[0]))):
if self.lca_table[u][i] != self.lca_table[v][i]:
u = self.lca_table[u][i]
v = self.lca_table[v][i]
return self.parent[u]
def update_taxes(self, a, b, c, operation):
# Implement the logic to update taxes along the path from a to b
lca_node = self.lca(a, b)
# Update path from a to lca
self._update_path(a, lca_node, c, operation)
# Update path from b to lca
self._update_path(b, lca_node, c, operation)
def _update_path(self, node, target, c, operation):
while node != target:
if operation == 1: # Increase tax
self.nodes[node].tax = max(self.nodes[node].tax, c)
elif operation == 2: # Decrease tax
self.nodes[node].tax = min(self.nodes[node].tax, c)
node = self.parent[node]
if node == target:
if operation == 1:
self.nodes[node].tax = max(self.nodes[node].tax, c)
elif operation == 2:
self.nodes[node].tax = min(self.nodes[node].tax, c)
def sum_taxes(self, a, b):
lca_node = self.lca(a, b)
return self._sum_path(a, lca_node) + self._sum_path(b, lca_node) - self.nodes[lca_node].tax
def _sum_path(self, node, target):
total = 0
while node != target:
total += self.nodes[node].tax
node = self.parent[node]
if node == target:
total += self.nodes[node].tax
return total
# Пример использования
n = 5
taxes = [1, 2, 3, 4, 5]
kingdom = Kingdom(n, taxes)
# Добавление дорог
kingdom.add_edge(0, 1)
kingdom.add_edge(1, 2)
kingdom.add_edge(1, 3)
kingdom.add_edge(3, 4)
# Запускаем DFS для подготовки LCA
kingdom.dfs(0, -1, 0)
kingdom.prepare_lca()
# Обработка запросов
kingdom.update_taxes(0, 2, 5, 1) # Увеличить налоги по пути от 0 до 2 до 5
print(kingdom.sum_taxes(0, 2)) # Сумма налогов по пути от 0 до 2