Overview

This problem asks you to find the path between two points on a tree and, for each query, compute the length of the Longest Strictly Decreasing Subsequence (LDS) of the altitude sequence along that path.

Analysis

Problem Decomposition

This problem can be broken down into two major steps:

1. Finding the path between two points on a tree: Since it is a tree structure, the path between any two points \(u, v\) is uniquely determined. This path goes from \(u\) through the LCA (Lowest Common Ancestor) to \(v\).
2. Computing the Longest Strictly Decreasing Subsequence of the altitude sequence: We compute the LDS of the sequence of altitudes at points along the path, listed in order.

Reducing LDS to LIS

The Longest Strictly Decreasing Subsequence (LDS) can be reduced to a Longest Strictly Increasing Subsequence (LIS) problem by negating (multiplying by \(-1\)) each element of the sequence.

• Original sequence: \(h_1 > h_2 > \cdots > h_m\) (strictly decreasing)
• After negation: \(-h_1 < -h_2 < \cdots < -h_m\) (strictly increasing)

LIS can be efficiently computed using the well-known \(O(k \log k)\) algorithm (using bisect_left).

Complexity Estimation

• \(N, Q \leq 5000\), which is relatively small.
• The path length is at most \(O(N)\).
• Even if we construct the path and compute the LIS for each query, it takes \(O(N \log N)\) per query, and \(O(QN \log N)\) overall, which is well within the time limit.

Algorithm

1. LCA (Lowest Common Ancestor) Preprocessing

We preprocess using Binary Lifting (Doubling) to answer LCA queries in \(O(\log N)\).

• up[k][v]: The vertex reached by following the parent edge \(2^k\) times from vertex \(v\)
• depth[v]: The depth from the root (point \(1\))

How to find the LCA: 1. Equalize the depths of \(u\) and \(v\) (lift the deeper one up) 2. Lift both simultaneously to find the point where they meet

2. Path Construction

Find the path from \(u\) to LCA \(l\) and the path from \(v\) to LCA \(l\), then concatenate them.

• \(u \to l\): Follow parents from \(u\) to \(l\) in order → \([u, \ldots, l]\)
• \(l \to v\): Follow parents from \(v\) to \(l\), then reverse → \([\) child after \(l\), \(\ldots, v]\)

Concatenating gives the path \([u, \ldots, l, \ldots, v]\).

3. Computing the LDS

Given the altitude sequence along the path \(h_1, h_2, \ldots, h_k\):

1. Negate each element to get \(-h_1, -h_2, \ldots, -h_k\)
2. Compute the strictly increasing LIS of this sequence
3. Apply the standard \(O(k \log k)\) LIS algorithm using bisect_left with a tails array

Concrete example: If the altitudes along the path are \([10, 5, 8, 3, 7, 2]\): - Examples of strictly decreasing subsequences: \([10, 8, 3, 2]\) (length 4), \([10, 5, 3, 2]\) (length 4) - The longest has length 4

Complexity

• Time complexity: \(O(N \log N + Q \cdot N \log N)\)
  • LCA preprocessing: \(O(N \log N)\)
  • Each query: Path construction \(O(N)\) + LIS computation \(O(N \log N)\)
  • Overall: \(O(QN \log N)\) (since \(Q, N \leq 5000\), this is less than approximately \(3 \times 10^8\))
• Space complexity: \(O(N \log N)\) (doubling table)

Implementation Notes

• Using bisect_left for strictly increasing LIS: bisect_left returns “the first position with a value greater than or equal to the target,” so equal values are overwritten, correctly handling strict monotonic increase. If you wanted non-strict (\(\leq\)), you would use bisect_right, but since this problem requires strict inequality, bisect_left is appropriate.

• Beware of duplication when concatenating paths: The path \(u \to \text{LCA}\) includes the LCA itself, while the path \(v \to \text{LCA}\) excludes the LCA before reversing and concatenating. This prevents the LCA from being included twice.

• The case \(u = v\): The path consists of a single point, and the LDS length is \(1\). No special handling is needed, as the general algorithm naturally handles this case.

  Source Code

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    if N >= 2:
        for i in range(2, N + 1):
            p = int(input_data[idx]); idx += 1
            parent[i] = p
            children[p].append(i)
    
    # Precompute LCA using binary lifting
    LOG = 13
    up = [[0] * (N + 1) for _ in range(LOG)]
    depth = [0] * (N + 1)
    
    # BFS to compute depth and up[0]
    from collections import deque
    queue = deque([1])
    visited = [False] * (N + 1)
    visited[1] = True
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for c in children[v]:
            if not visited[c]:
                visited[c] = True
                depth[c] = depth[v] + 1
                up[0][c] = v
                queue.append(c)
    
    for k in range(1, LOG):
        for v in range(1, N + 1):
            up[k][v] = up[k-1][up[k-1][v]]
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                u = up[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]
    
    def get_path(u, v):
        l = lca(u, v)
        # Path from u to l
        path_u = []
        node = u
        while node != l:
            path_u.append(node)
            node = up[0][node]
        path_u.append(l)
        # Path from l to v (reversed)
        path_v = []
        node = v
        while node != l:
            path_v.append(node)
            node = up[0][node]
        # path is path_u + reversed(path_v)
        path_v.reverse()
        return path_u + path_v
    
    def lds_length(seq):
        # Longest strictly decreasing subsequence
        # = LIS of negated sequence (strictly increasing)
        # For strictly increasing LIS, use bisect_left on tails
        if not seq:
            return 0
        # We want longest strictly decreasing subsequence
        # Transform: negate values, find longest strictly increasing subsequence
        neg_seq = [-x for x in seq]
        # LIS strictly increasing
        tails = []
        for x in neg_seq:
            pos = bisect_left(tails, x)
            if pos == len(tails):
                tails.append(x)
            else:
                tails[pos] = x
        return len(tails)
    
    out = []
    for _ in range(Q):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        path = get_path(u, v)
        heights = [H[node] for node in path]
        out.append(str(lds_length(heights)))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.