首页 > 试题广场 >

树上上升序列

[编程题]树上上升序列

热度指数：1485 时间限制：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

输入

输出

算法知识视频讲解

小牛冲冲冲jiang

发表于 2021-09-28 18:52:53

需要自己创建树的数据结构有向无环图dfs import java.util.Scanner; import java.util.*; import java.io.*; public class Main { private static int max = 0; privat 展开全文

zhangbw_

发表于 2023-03-14 20:15:55

C++ 有向图 + 记忆化搜索建立有向图：u，v为树上的一条边当v的权值大于u的权值时，增加一条u到v的边当u的权值大于v的权值时，增加一条v到u的边 dp[u] : 以u为起始顶点的最长递增路径长度。 #include <bits/stdc++.h> using 展开全文

想要睡觉

发表于 2023-05-11 16:57:41

#include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; long long n, m, k, t; 展开全文

牛客405485524号

发表于 2022-09-17 10:40:15

#大佬解答下为何有部分算例不能通过 import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.LinkedList; import java.util.List; im 展开全文