Помогите, пожалуйста, pyhton/c++/c#

Question

Помогите, пожалуйста, pyhton/c++/c#

Ann Chp Ученик (95), открыт 3 недели назад

Структура королевства — дерево, т.е. королевство состоит из 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 . Пожалуйста, помогите ответить на все запросы.

Answer 1

 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