I wonder if we can solve this problem ?

Given a DAG $$$(n <= 3e5, m <= 3e5)$$$ and $$$Q$$$ queries $$$(Q <= 3e5)$$$ $$$u$$$ $$$v$$$, determine if $$$u$$$ is ancestor of $$$v$$$ in DAG

I was wondering if we could implement Prim's algo in O(n log n) (n is number of vertices)

Hi guys.

I have a problem want to ask you guys.

Problem: Given a tree with n nodes, m segments in a tree with 2 endpoints. Find the maximum number of segments satisfy that not exist two segments with the edge intersect. (n < 1e3, m < 1e5);

My solution (WA passed 4/5) is: Sort m segments by the depth of their LCA. If two segments have the same LCA, if one of them have the endpoint equal to their LCA i choose it ,else i choose the one have shorter length. After sorted, i pick it one by one.

My sub For example:

n = 6, m = 4;

edges:

1 2

2 3

3 4

3 5

3 6

segments:

1 3

4 5

5 6

6 4

So the answer is 2 because we can choose segment (1, 3) and segment (4, 5) as path 1 -> 3 = 1 -> 2 -> 3, path 4 — > 5 = 4 — > 3 -> 5.

You also can choose (1, 3), (5, 6) or (1, 3), (6, 4)