Binary search on K. Let dp[u] = max length path coming out of subtree u. Then, we have two cases depending on the parity of the number of children of u.

Odd:

We should choose one path to extend out of u and pair the other paths together. We can do this with multisets or binary search.

Even: We could pair all paths together, or we could have one path end at u, have one path extend out of u, and pair all other paths together. The way to choose the path to extend out of u is similar to the odd case.

Code: https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_3P/Deleg.cpp

WLOG, x1<x2<x3, y1<y3<y2. We can prove that there is a center (xc, yc) such that x2=xc, y2=yc+k, x3=xc+k, y3=yc, x1=xc-a, y1=yc-b, a+b=k, for some k. We just iterate over all xc, yc, and k. We can find the number of (x1, y1) with diagonal prefix sums. Code: https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_3P/Triangles.cpp

There are two ways to do this: 1. Maintain the sum for each power in a DP. 2. Count the number of k-tuples of rightmost segments of connected components. This can be done by finding the number of i-tuples with increasing indexes using DP, then using some combinatorics to find the number of k-tuples.

Both DP solutions are optimized with segment trees.

Code (solution 2): https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_3P/Help.cpp