首页 > 试题广场 >

树上上升序列

[编程题]树上上升序列

热度指数：1495 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

度度熊给定一棵树，树上的第 $\mathit u$ 个节点有点权 $a_{u}$ 。请你找出一条最长的路径 $\mathit (u,v)$ ，使得从 $\mathit u$ 沿着唯一路径走到 $\mathit v$ 的途中，点权不断严格递增。
换句话说，设路径为 $(u,p_{1},p_{2}, \dots ,p_{m} , v)$ ，则需要满足 $a_{u} < a_{p_{1}} < a_{p_{2}} \dots < a_{p_{m}} < a_{v}$ 。输出最长满足条件的路径的长度。

输入描述:

第一行树的节点个数 , 接下来一行个数字，表示每个点的点权。接下来行，每行两个数代表树上的一条边，连接点。
.

输出描述:

一行一个数字表示答案，即最长的长度。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

Python

随机ID

树形DP

def solve():
    n = int(input())
    weights = list(map(int, input().split()))
    from collections import defaultdict
    edges = defaultdict(list)
    for _ in range(n-1):
        u, v = map(int, input().split())
        edges[u-1].append(v-1)
        edges[v-1].append(u-1)
    dp = [-1] * n 

    def helper(root):
        if dp[root] != -1:
            return dp[root]
        res = 1
        for nxt in edges[root]:
            if weights[root] < weights[nxt]:
                res = max(res, 1+helper(nxt))
        dp[root] = res 
        return res 

    for i in range(n):
        helper(i)
    print(max(dp))
solve()

发表于 2021-10-18 16:03:20 回复(0)