P4319 变化的道路

小 w 和小 c 在 H 国，近年来，随着 H 国的发展，H 国的道路也在不断变化着 根据 H 国的道路法，H 国道路都有一个值 $w$，表示如果小 w 和小 c 通过这条道路，那么他们的 L 值会减少 $w$，但是如果小 w 和 小 c 在之前已经经过了这条路，那么他们的 L 值不会减少 H 国有 $N$ 个国家，最开始 H 国有 $N-1$ 条道路，这 $N-1$ 条道路刚好构成一棵树 小 w 将和小 c 从 H 国的城市 1 出发，游览 H 国的所有城市，总共游览 32766 天，对于每一天，他们都希望游览结束后 L 值还是一个正数， 那么他们出发时 L 值至少为多少 H 国的所有边都是无向边，没有一条道路连接相同的一个城市

无

无

第一天，选择 1 -(1)> 2 -(0)> 1 -(3)> 3 -(2)> 4，L 值总共减少了 6，所以 L 值至少为 7 第二天，选择 1 -(1)> 2 -(0)> 1 -(3)> 3 -(4)> 4，L 值总共减少了 8，所以 L 值至少为 9 第三天及之后，选择 1 -(3)> 3 -(4)> 4 -(5)> 2，L 值总共减少了 12，所以 L 值至少为 13 subtask1 : 15分，$N = 100, rm = 233$ subtask2 : 15分，$N = 1000, rm = 2333$ subtask3 : 20分，$N = 49998, rm = 32766, l = r$ subtask4：20分，$N = 49999, rm = 32766, r = rm$ subtask5：30分，$N = 50000, rm = 32766$ 对于subtask3 : $M = rm$，对于其他subtask：$M=3\times rm$ 对于所有数据 : $1\leq N\leq 50000, 1\leq l\leq r\leq rm\leq 32766, 1\leq w\leq 10^9$