树上上升序列

//邻接表
import java.util.*;

public class Main {
    static List<List<Integer>> graph = new ArrayList<>();
    static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }
        for (int i = 0; i < num.length; i++) {
            graph.add(new ArrayList<>());
        }
        // 构建图,邻接矩阵
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        for (int i = 0; i < num.length - 1; i++) {
            dfs(num, i, 1);
        }
        System.out.println(max);

    }

    public static void dfs(int[] num, int start, int wayNum) {
        max = Math.max(max, wayNum);
        for (int i : graph.get(start)) {
            if (num[i] > num[start]) {
                dfs(num, i, wayNum + 1);
            }
        }
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Author: LI
 * @Date: Created in 14:34 2022/9/13
 */

class TreeNode {
    int weight;
    List<TreeNode> friend;

    public TreeNode(int weight) {
        this.weight = weight;
        friend = new ArrayList<>();
    }
}

public class Main {
    static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new TreeNode(sc.nextInt());
        }
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            nodes[a].friend.add(nodes[b]);
            nodes[b].friend.add(nodes[a]);
        }

        for (TreeNode node : nodes) {
            dfs(node, 1);
        }
        System.out.println(max);
    }

    private static void dfs(TreeNode node, int preSum) {
        max = Math.max(max, preSum);
        for (TreeNode friend : node.friend) {
            if (friend.weight > node.weight) {
                dfs(friend, preSum + 1);
            }
        }
    }
}

// golang
package main
import (
    "fmt"
)
/*
实际上是舍弃无向图中至少一半的边变成树或森林，
而且最长路径不一定是从树的根节点出发。
*/
func main() {
    n := 0
    _, err := fmt.Scan(&n)
    if err != nil{
        fmt.Println(0)
        return
    }
    w := make([]int, n+1)
    for i:=1;i<=n;i++ {
        wi := 0
        _, err := fmt.Scan(&wi)
        if err != nil{
            break
        }
        w[i] = wi
    }
    m := make(map[int] map[int]struct{})
    child := make([]bool, n+1)
    for {
        var s, t int
        _, err := fmt.Scan(&s, &t)
        if err != nil{
            break
        }
        if w[s] == w[t] {
            continue
        }
        if w[s] > w[t] {
            s, t = t, s
        }
        if _, ok := m[s]; !ok {
            m[s] = map[int]struct{}{}
        }
        m[s][t] = struct{}{}
    }
    ret := 0
    for i:=1;i<=n;i++ {
        last := []int{i}
        cret := 0
        for len(last) > 0 {
            cret++
            cur := []int{}
            for i := range last {
                s := last[i]
                for t, _ := range m[s] {
                    cur = append(cur, t)
                }
            }
            last = cur
        }
        if cret > ret {
            ret = cret
        }
    }
    fmt.Println(ret)
}

def dfs(cur,src,step):
    if book[cur]>step:
        return None
    book[cur] = step
    for neighbor in adjList[cur]:
        if neighbor!=src and weight[neighbor]>weight[cur]:
            dfs(neighbor,cur,step+1)
n = int(input())
weight = [0]
w = input()
for i in w.split(" "):
    weight.append(int(i))
adjList = [[] for i in range(n+1)] #把树当成图，构建邻接表
for i in range(n-1):
    a,b = map(int,input().split(' '))
    adjList[a].append(b)
    adjList[b].append(a)
book = [1 for i in range(n+1)]
for i in range(1,n+1):
    dfs(i,0,1)
    #print(book)
maxStep = 1
for i in range(1,n+1):
    maxStep = max(maxStep,book[i])
print(maxStep)

树形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()

import sys
class Node(object):
    def __init__(self, val) -> None:
        self.val = val
        self.childs = []

n = int(input().strip())
nodes = list(map(lambda x:Node(val=int(x)), input().strip().split()))
for line in sys.stdin:
    if line.strip() == "":
        break
    father, child = map(int, line.strip().split())
    father, child = child-1, father-1
    nodes[father].childs.append(nodes[child])

res = float('-inf')

def dfs(node):
    global res
    if node == None:
        return 0, 0
    inc, dec = 0, 0
    
    for child in node.childs:
        cinc, cdec = dfs(child)
        if node.val > child.val:
            inc = max(inc, cinc)
        elif node.val < child.val:
            dec = max(dec, cdec)

    res = max(res, inc + dec + 1)
    #print(res)
    return inc + 1, dec + 1

dfs(nodes[0])
# print("result: {}".format(res))
print(res)