全問ちょっとずつ解説と違う…
問題
コンテストサイト
公式解説
A
木の重心 $g$ を取ります。 $g$ に隣接する頂点を $v_1,v_2,\ldots$ とします。 $g$ から見て $v_k$ 側にある頂点（ $g$ を含む）全体から誘導される部分木を $T_k$ とします。 $T_k$ 内に住む人が $g$ まで行くのにかかる時間を計算し、その最大値を $X_k$ とします。
集合地点を $T_k$ 内に取った時、 $T_k$ の外に住む人が集合するまでの時間は、 $X_j$ ($j\neq k$)より小さくなりません。よって、 $X_k$ が最大であるような $k$ をとると、集合地点は $T_k$ 内にあるとしてもよいです。
以降、集合地点としてありうる範囲の重心を $g$ として繰り返すと、最終的には集合地点がどの辺上にあるかを特定できます。その後は例えば二分探索で解が求まります。
B
完全なソートに必要な操作回数からの差を考えます。
ソート後の状態に与えられた自由度は、完全ソート後の状態に対して左から右の順に任意で隣接スワップを行うことで表せます。これによる必要な操作回数の変化は、転倒数の差として簡単に求まります。具体的には交換する $2$ 要素が初期状態において左からそれぞれ $a$ , $b$ 番目にあるとき、 $a\lt b$ ならば操作回数に $+1$ 、 $a\gt b$ ならば操作回数に $-1$ されます。
初期状態で左から $i$ 番目に $a$ があるとき $B_a=i$ とします。
左から $k$ , $k+1$ 番目の要素の交換のときに操作回数に $-1$ できる必要条件は、 $\max_{i\leq k}B_k\gt B_{k+1}$ です。そしてこの必要条件もとで操作回数としてあり得る最小値は達成可能です。
C
クエリ区間の Cartesian Tree の高さが答えです。 Cartesian Tree の根は区間最大値クエリで求まります。あとは、根から子をたどる操作の最大値が解です。
左→左→……→左→右→…… の順に子をたどるとします。 左→右 が起こった後は、移動できる区間がそれまでの経路にかかわらないので、あらかじめ計算できます。これは列全体の Cartesian Tree の各ノードについての計算なので $O(N)$ 通りであり、 DP で計算量 $O(N)$ になります。
左に連続で移動するとき、各ノードの移動元が一意になるので、すべてのノードにポテンシャルを置けばその差で移動回数を表せます。区間を $[L,R)$ 、始点を $M$ としたとき、左に $1$ 回以上移動したときの終点は $[L,M)$ に入ります。
よって、 DP の解にポテンシャルを足し、その区間 $[L,M)$ に対して区間最大値クエリを使えばこの移動パターンのときの移動回数の最大値がわかります。