面白かった！！！
ツリーネタでまだこういうのが残ってるんだね！！！
問題概要
頂点の木が与えられる。
いま、木の頂点を 3 つ選ぶ (a, b, c とする)。このとき、
- a と b を結ぶパスに含まれている辺集合
- b と c を結ぶパスに含まれている辺集合
- c と a を結ぶパスに含まれている辺集合
の和集合のサイズとして考えられる最大値を求めよ。また、それを実現する具体的な 3 頂点も出力せよ。
制約
考えたこと
もし 3 つ選ぶのではなく 2 つだったら直径を求める問題ということになる。3 つであっても
- 直径を求める
- 直径から最も距離の離れた頂点を求める
とすればよいのでは...という直感がはたらく。反例はなさそうだけど一応簡単に証明してみる。
まず、ある 1 点 v が存在して、求める辺集合は
- v-a パス
- v-b パス
- v-c パス
という風に分解できることに着目する。そうすると実はこの問題は
木の 1 頂点 v を決めうちしたときには、v から各点への距離のベスト 3 を a, b, c とすればよい
v を全頂点について試せばよい
ということがわかる。そう考えると全方位木 DP で解くこともできる。
全方位解はかなりそのままで、3点の合流点を決め打つとその点を根として1番遠い3点(ただしどの2つも同じ部分木にない)を選べばいいので、直径を求める全方位を書いたことがあればそれと全く同様にできる
— てんぷら (@tempura_cpp) 2020年1月22日
ここでは直径を利用する方向へと考察を進めてみた。まず直径 p-q を 1 つとってみる。このとき、いかなる「ハブ点 v と、そこからの距離ベスト 3 の点 a, b, c」の組合せに対しても、解を悪化させることなく「直径 p-q を含む解」に変形できることがいえれば OK。以下の議論はだいぶごちゃごちゃしてしまっているけど、もう少しスマートにできるのかもしれない。
もし p-q が、v-a, v-b, v-c のいずれとも接点を持たない場合には、v からパス p-q へと向かって行ってたどり着く p-q 上の点を w とする。このとき、v-a 間と、v-b 間を削り取ってしまって、代わりに w をハブ点としてw-p 間、w-q 間、w-c 間を考えてみると、直径の定義から、元のサイズより悪化することはない。
次に、p-q が v-a, v-b, v-c のいずれかと交点をもつときを考える。p から q へと向かうときに最初に交わる点 w が v-a 上の点と仮定して一般性を失わない。このとき直径の定義から、w-q 間が w-a 間より短いことはありえないので、w-q を w-a に組み替えてしまっても良い。この時点で v-p, v-b, v-c の状態になっている。
次に q から p へと向かうときに最初に交わる点 x がどこにあるかで場合分けする
v-p 間の点 x で分岐するとき、v-c をなくして x-q を付け加えることで解が悪化することはない (ハブ点が v から x へと入れ替わる)
v-b 間の点 x で分岐するとき、x-b をなくして x-q を付け加えることで解が悪化することはない
v-c 間の点 x で分岐するとき、x-c をなくして x-q を付け加えることで解が悪化することはない
入り組んでしまったが、いかなる「ハブ点 v と、そこからの距離ベスト 3 の点 a, b, c」の組合せに対しても、解を悪化させることなく「直径 p-q を含む解」に変形できることがわかった。
以上をまとめると、以下のようにして解くことができる。
- 直径を求める
- 直径からの距離が最大の点を求める
#include <iostream> #include <vector> #include <algorithm> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } using Graph = vector<vector<int>>; int N; Graph G; struct Diameter { vector<int> prev; pair<int,int> DiameterDFS(const Graph &G, int v, int p) { pair<int,int> res(v, 0); for (int i = 0; i < (int)G[v].size(); ++i) { if (G[v][i] == p) continue; pair<int,int> tmp = DiameterDFS(G, G[v][i], v); tmp.second++; if (tmp.second > res.second) res = tmp, prev[G[v][i]] = v; } return res; } vector<int> solve(const vector<vector<int> > &G) { prev.assign((int)G.size(), -1); pair<int,int> leaf = DiameterDFS(G, 0, -1); prev.assign((int)G.size(), -1); pair<int,int> t = DiameterDFS(G, leaf.first, -1); vector<int> res; int cur = t.first; while (cur != -1) res.push_back(cur), cur = prev[cur]; return res; } }; vector<int> depth; void rec(int v, int p) { depth[v] = depth[p] + 1; for (auto ch : G[v]) { if (ch == p) continue; rec(ch, v); } } void solve() { Diameter Dia; auto di = Dia.solve(G); // 直径から各頂点への距離を求める depth.assign(N, 0); for (int i = 1; i+1 < di.size(); ++i) { int v = di[i]; for (auto to : G[v]) { if (to == di[i-1] || to == di[i+1]) continue; rec(to, v); } } int a = di[0], b = di.back(), c = -1; int ma = 0; for (int v = 0; v < N; ++v) if (chmax(ma, depth[v])) c = v; if (c == -1) for (int v = 0; v < N; ++v) if (v != a && v != b) c = v; printf("%d\n", ma + (int)di.size() - 1); printf("%d %d %d\n", a+1, b+1, c+1); } int main() { scanf("%d", &N); G.assign(N, vector<int>()); for (int i = 0; i < N-1; ++i) { int u, v; scanf("%d %d", &u, &v); --u, --v; G[u].push_back(v); G[v].push_back(u); } solve(); }
