贪心（Python）

思路：贪心。为了保证根节点具有最大的生命值，我们可以用一个贪心策略：大剪刀能用次，那么就在前m层使用大剪刀，后更深的层使用小剪刀即可。并且题目说了，每次修剪为左右孩子到根，这个顺序天然和后序遍历一致。因此，我们就可以递归算一遍后序遍历，以及对应节点的深度；之后，再用贪心策略求出最终的答案并输出即可

注意：递归这里python有可能超时，推荐用模拟栈来写。模拟栈的后序遍历有两种写法：1.先序遍历改一下孩子的访问顺序，最后整体翻转；2.额外用state状态变量进行标记

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n = II()
    ls = [0] * (n + 1)
    rs = [0] * (n + 1)

    cnt = 0
    for u in range(1, n + 1):
        l, r = MII()
        ls[u], rs[u] = l, r
        if l != 0:
            cnt += 1

    a = [0] + LII()
    m = (cnt + 1) // 2

    depth = [0] * (n + 1) # 存放节点深度
    order = [] # 存放后序遍历
    stack = [(1, 0, 1)]  # (节点, 状态, 深度)

    while stack:
        u, state, d = stack.pop()
        if state == 0:
            depth[u] = d
            stack.append((u, 1, d))
            if ls[u] != 0:
                stack.append((rs[u], 0, d + 1)) # 由于栈是后进先出，所以先入右
                stack.append((ls[u], 0, d + 1)) # 后入左，后续处理时左先弹出
        else:
            order.append(u)

    # 题目的操作天然就是左右根，符合后序遍历
    for u in order:
        if ls[u] == 0:
            continue

        l, r = ls[u], rs[u]
        if depth[u] <= m: # 贪心，上m层用大剪刀
            a[u] = fmax(a[l], a[r])
        else: # 下面更深的层用小剪刀
            a[u] = fmin(a[l], a[r])

    print(a[1])

t = 1
# t = II()
for _ in range(t):
    solve()