A. Phone Numbers
長さと 8 の個数から計算できます．
B. Maximum Sum of Digits
適当に $1$ を渡すことを考えると，$a$ の $1$ の位は $0$ または $9$ としてよいです．$10$ の位以降についても同じことがいえます．これで全探索可能です．より強く $9999$ の形に限定してよいこともいえます．
C. Maximum Subrectangle
$c$ の矩形和は $a$ の区間和と $b$ の区間和の積です．長さごとの区間和の最小値をそれぞれ求めておけばよいです．
D. Social Circles
円環をいくつ作ってもよいことに注意．ある人の $l$ と他の人の $r$ が同じ区間に対応するときにこれら $2$ 人をマッチさせる有向辺を作ると，すべての人の入次数・出次数が $1$ になっていくつかの円環ができます．よって，$l_i$ 全体の $r_j$ 全体のマッチングで $\sum\max(l_i,r_j)$ が最小であるものを作ればよいです．これはソートして対応させればよいことが証明可能です（$n=2$ のときにチェックしたらあとは exchange argument で）．
E. Sergey and Subway
2 点のもとの距離を $d$ とすると，変換後の距離は $\lceil d/2\rceil$ になります．この和を求めればよいです．木 dp して奇数長・偶数長のパスの cnt, sum を管理する形で $O(N)$ 時間で解けます．
ライブラリが充実している人は https://judge.yosupo.jp/problem/frequency_table_of_tree_distance を使うのも簡単です（$O(N\log^2N)$ 時間）．
F. Shrinking Tree
操作は辺縮約に関する問題ですが，
- 初期状態は辺がない．連結成分にラベルを持たせておく．
- 辺をランダムに選んで張る．両成分のラベルを等確率で選んで採用．
と考えた方が分かりやすいと思います．目標頂点を決めて $N$ 回解くことにすると，辺を張る操作のうち根を含む連結成分に対するものの重みを $1/2$ として計算すればよいです．
木 dp を各 subtree では，「subtree 内の操作を何回したときに subtree root が全体の根と同じ成分になるか」を固定した場合の解を計算します．
G. Balls and Pockets
逆操作を考えると，「写像 $f$ があるのでいろんな $(x,k)$ に対して $f^k(x)$ を計算せよ」というタイプの問題になります．$f$ は，おおよそ「非負整数全体が $n+1$ 個の区間に分かれている．$0$ based index で $i$ 番目の区間では $f(x)=x+i$」というような形になっています．
$(x,k)$ を固定するとシミュレーションできて，$c_1,c_2,\ldots,c_n$ があって，$i=0,1,\ldots,n$ の順に「はじめて $c_{i+1}$ 以上になるまで」をシミュレーションします．
すべてのクエリ $(x,k)$ に対して同時にこのシミュレーションをすることを考えます．クエリは $x$ でソートされていると考えます．差が $i$ 以下になったクエリはまとめて動かせます．
「先頭と同じ成分になるクエリが増えるところまでシミュレーション」「$c_{i+1}$ を超えるところの処理」「$k=0$ になったクエリを取り出して答の計算」などのイベントを $O(N+Q)$ 回処理すればよいことが分かります．
これはすべて適切な平衡二分木を使えば達成できます．split, merge, $x$ での二分探索に加えて，$(x,k)$ に対する定数加算と $k$ の最小値取得加算あたりが出来るとよいはずです．
H. Sophisticated Device
加算と $d$ 乗ができるときに積を作れということです．
加算を $\log(p)$ 回で，定数倍もできることになります．
$d=2$ の場合を考えると，$2xy=(x+y)^2-x^2-y^2$ から積が作れます．一般に，$2$ 乗が作れればよいことになります（積が計算できるならば $2$ 乗も計算できないといけないので $2$ 乗を作ろうという方針決め打ちでよいです）．これで入力がひとつだと思えばよくなって考えやすくなりました．
$x^d, (x+1)^d, \ldots, (x+d)^d$ は線形独立なので，$x^2$ はこれらの線形結合で書けます．線形結合で書く係数は連立方程式を解けば分かります．
