解答
思路1 直接求树上路径的交
将路径按长度排序，设最长的路径长度为(L)。对递增的(k)，求前(k)大路径的交中边的最大值(M)，第(k+1)长路径的长度为(N)，答案与(max{L-M,N})取最小值。
正确性：考虑一个合法的解，设它在前(k)条路径上，则其必不在第(k+1)条（如果有的话）路径上。
我的做法
设要求(P_1=(u_1, v_1))以及(P_2=(u_2,v_2))这两条路径的交(P=P_1cap P_2=(u,v))。
先考虑(P_1)，(P_2)都是链的情况（不妨设(v_1,v_2)分别为(u_1,u_2)的祖先）。
此时，考虑入栈序(I)与出栈序(O)：一个点(x)在(P_i)上当且仅当其满足(I_{u_i} le I_x le I_{v_i})与(O_{u_i} ge O_x ge O_{v_i})。（可以用二维线段树解决（雾））
考虑实际图形（设(dep_{v_1}le dep_{v_2})）。
先考虑在什么时候交为空。显然，在(v_1)与(v_2)不存在一个在另一个的子树里的时候交为空。但是，它不是充分必要条件（例如，(v_1)是(v_2)的某个其他儿子）。原题设的充分必要条件是“(v_1)不在(P_2)上”，所以我们在预处理时处理出入栈出序列，查询时直接比较即可。易知(P)中(u=LCA(u_1,v_1), v = v_1)。
若(P_1,P_2)都不简单：暴力转化成四对链的交的并。（常数极大）
注意题面里面没有保证(u e v)。
route merge(route R, route r) {
if (R.empty() && r.empty()) return NO;
else if (R.empty()) return r;
else if (r.empty()) return R;
else {
R.clean(), r.clean();
if (R.v == r.v) return (route){R.u, r.u};
else assert(0);
}
}
route inter(route R, route r) {
if (R.empty() || r.empty()) return NO;
R.clean(), r.clean();
int L = lca(R.u, R.v).first, l = lca(r.u, r.v).first;
if (L == R.v && l == r.v) {
if (dep[L] < dep[l]) {
swap(L, l);
swap(R, r);
}
if (din[r.v] <= din[R.v] && din[R.v] <= din[r.u] && dout[r.v] >= dout[R.v] && dout[R.v] >= dout[r.u]) return route(lca(R.u, r.u).first, L);
else return NO;
}
if (L == R.v) {
swap(R, r);
swap(L, l);
}
return merge(inter(route(R.u, L), r), inter(route(R.v, L), r));
}
神犇wygz的做法
由于算法会把路径的交作为下一次的路径，所以如果对每条边进行考虑的话，复杂度有均摊保证。
首先，找出长度最大的路径上的所有边，将它们放入大根堆中（键值为边权）。
之后，从大到小枚举路径，考虑当前堆中的最大边是否在当前路径中，不在则弹出，以此类推。
代码难度较小……
思路2 二分答案（求长度大于答案的所有线段的交中的最大边权来验证答案）
因为最小值有点难求（且显然满足单调性），考虑将其转化为判定性问题。
由于二分答案只有(log)次，所以求线段的交可以(O(m+n))。对一条路径((u,v))，tag[u]++, tag[v]++, tag[lca(u,v)]-=2即可。
之后，dfs整棵树，经过一条边时判断是否被所有选择的路径覆盖即可。（一条边被路径覆盖的次数=末端点子树的权值和）