Solution¶

We use the lemma stating the necessary and sufficient condition for an ancestor-descendant relationship as follows: \(stt[u]<=stt[v] and fnt[v]<=fnt[u]\) or \(stt[u]<=stt[v] and stt[v]<fnt[u]\)

The validity of this lemma can be easily verified. To solve the problem, we first perform a DFS traversal on the tree. Then, for each query, we check the aforementioned condition in \(O(1)\) time.

Solution¶

First, find the p-th ancestor of vertex v similar to the previous problem. Name this vertex w. Now, the answer is the number of vertices u where:

That is, in the vector corresponding to vertex v, we want the count of starting times within a specific interval, which can be solved with a simple binary search.

# p-th ancestor of vertex v
w = find_pth_ancestor(v, p)
# The answer is the number of u's such that...
answer = count_us(h, v, w)
# In the vector corresponding to v's height group:
group = height_group[h[v]]
# Binary search for stt[w] <= stt[u] < fnt[w]
left = bisect_left(group, stt[w])
right = bisect_left(group, fnt[w])
return right - left

Answer¶

The minimum number of operations required is \(k\). One optimal strategy is to pair the leaves appropriately. For example, perform a DFS traversal and pair leaves based on their discovery order.

1void color_edges(Tree T) {
2    vector<Leaf> leaves = T.get_leaves();
3    // For trees with 2k leaves, at most k operations are needed
4    for (int i = 0; i < leaves.size() / 2; i++) {
5        // Color the path between i-th and (i+k)-th leaf
6        auto path = T.find_path(leaves[i], leaves[i + k]);
7        path.color_edges();
8    }
9}

Explanation: Pairing diametrically opposite leaves (in a DFS order) ensures each edge is colored exactly once. This works because every internal edge lies on exactly one such path when leaves are paired systematically. Time complexity remains \(O(n)\).

Solution¶

Answer = k In the following, we present the method and prove its correctness. If n=2, the problem is trivially solved. Therefore, assume n>2 and there exists at least one non-leaf vertex. Root the tree at a non-leaf vertex and number the leaves according to their starting times. Now perform the following pairing on these leaves:

Clearly, the complexity of this pairing is \(O(n)\) .

Now we must show that all edges are colored. The subtree of each edge contains an interval of leaves. For an edge to be colored, there must exist a leaf pair where one end lies inside this interval and the other outside. Suppose the interval corresponding to the target edge is \([l, r]\) . We consider two cases:

First case: \(l \leq k\) and \(k+1 \leq r\) In this case: - If \(l \neq 1\), the pair \((1, k+1)\) falls inside the interval. - Otherwise, the pair \((k, 2k)\) will cover it.

Second case: If the interval doesn't match the first case, assume without loss of generality that \(l, r \leq k\) . In this case, the pair \((r, r+k)\) will color the edge.

Thus, in both cases the target edge is colored, and our constructed pairs are valid.