CF1192B Dynamic Diameter

有一个 $n$ 个点的带权无向树，$q$ 次操作，每次修改一条边的权值，要求在每次修改后，输出树的直径大小，强制在线。

第一行，$3$ 个由空格分隔的整数 $n,q,w$,（$2\le n\le 10^5$, $1\le q\le 10^5$, $1\le w\le 2\times 10^{13}$），代表有 $n$ 个点，$q$ 次修改，操作过程中每条边的最大权值为 $w-1$。 之后 $n-1$ 行，每行3个整数 $a，b，c$（$1\le a,b\le n$, $0\le c

输出 $q$ 行，每行一个整数，表示这次修改后树的直径。 ## 评分标准 子任务1（11分）$n,q\le 100,w\le 10000$ 子任务2（13分）$n,q\le 5000,w\le 10000$ 子任务3（7分）$w\le 10000$,树为以 $1$ 号点为中心的菊花图 子任务4（18分）$w\le 10000$,树为以 $1$ 号点为根的平衡二叉树 子任务5（24分）任意时刻存在一条树的直径经过 $1$ 号点 子任务6（27分）无特殊约定

The first sample is depicted in the figure below. The left-most picture shows the initial state of the graph. Each following picture depicts the situation after an update. The weight of the updated edge is painted green, and the diameter is red.  The first query changes the weight of the $ 3 $ rd edge, i.e. $ \{2, 4\} $ , to $ 1030 $ . The largest distance between any pair of vertices is $ 2030 $ – the distance between $ 3 $ and $ 4 $ . As the answer is $ 2030 $ , the second query is $$ d'_2 = (1 + 2030) \bmod 3 = 0 $$ $$ e'_2 = (1020 + 2030) \bmod 2000 = 1050 $$ Hence the weight of the edge $ \{1, 2\} $ is changed to $ 1050 $ . This causes the pair $ \{1, 4\} $ to be the pair with the greatest distance, namely $2080$ . The third query is decoded as $$ d'_3 = (1 + 2080) \bmod 3 = 2 $$ $$ e'_3 = (890 + 2080) \bmod 2000 = 970 $$ As the weight of the edge $ \{2, 4\} $ decreases to $ 970 $ , the most distant pair is suddenly $ \{1, 3\} $ with $2050$ .