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)