Codechef - Country Tour [CTOUR]

Encoderっていうコンテストの最後の問題
何気なく参加してみたけどこの問題は個人的に面白かった

問題

n頂点の木が与えられ、根は頂点1である
辺iは頂点a[i]とb[i]を繋ぎ、通る時c[i]円貰える
(c[i]が負のこともあり、そういうときは逆に-c[i]円払わないといけない)
q個のクエリが与えられるので、頂点a[i]からb[i]に行くまでに得られる金額の最大値 or 払わないといけない金額の最小値を求めよ
ただし、頂点aからbに移動する最中、向きを変えることが出来るのは一度だけである

※向きってのは根に向かって進む方向と根から離れる方向の2通りだけ考える
例えば1-2-3って木で3から2に向かう場合、1まで進んでから向きを変えて2に戻るって動きが出来る

解法

一直線にaからbに移動する場合のコストは、事前に頂点1と各頂点のパス上のコストの和を求めておき、aとbのLCAを求めることでO(logn)で求められる
向きを1度だけ変えられるってのを上手く利用して更にコストを増やしたい
始点aと終点bのLCAをvとする

・a=vのとき
aから根方向に進んで、コストが最大になるところで向きを変え、bまでまっすぐ進む
or bまで進んでから更に根と反対方向に進み続け、コストが最大になるところで向きを変え、bに戻る

・b=vのとき
aから根と反対方向に進んで、〜、bまで進む
or bまで進んでから更に根方向に進み続け、〜、bに戻る

・どちらでもないとき
aからvに進んでから更に根方向に進み続け、〜、vに戻り、そのままbまで進む

この3通りが考えられる
あとは各頂点から「根方向に進むときのコストの和の最大値」と「根と逆方向に進むときのコストの和の最大値」を求められれば解ける
これらはどちらも累積和っぽい再帰で求められる

int n, Q, a, b, c, pa[100100], ch[100100], s[100100];
vector<pair<int,int> > e[100100];
LCA lc;

int rec(int v, int p, int sum, int mn) {
	s[v] = sum, pa[v] = sum - mn;
	each(i,e[v]) if (i.first!=p) {
		int tsum = sum + i.second;
		int mx = rec(i.first, v, tsum, min(mn, tsum));
		chmax(ch[v], mx + i.second);
	}
	return ch[v];
}

signed main() {
	cin >> n >> Q;
	rep(i,n-1) {
		cin >> a >> b >> c;
		a--, b--;
		e[a].push_back({b,c}), e[b].push_back({a,c});
		lc.add(a,b);
	}
	rec(0,-1,0,0);
	lc.init(n,0);
	while (Q--) {
		cin >> a >> b;
		a--, b--;
		int v = lc.lca(a,b);
		int res = s[a] + s[b] - s[v]*2;
		if (a==v) res += max(pa[a], ch[b])*2;
		else if (b==v) res += max(ch[a], pa[b])*2;
		else res += pa[v]*2;
		cout << res << endl;
	}
}

https://www.codechef.com/ENCO2018/problems/CTOUR