AGC018 D : Tree and Hamilton Path(1100)
作成日：2017.07.26
最終更新日：2017.07.26
問題概要
$N$頂点の木は頂点$A_i,B_i$を結ぶ長さ$C_i$の辺を持つ。
この木において頂点$u,v$を結ぶ最短距離を$u,v$を結ぶ辺の長さとする$N$頂点の完全グラフを作る。
この完全グラフのハミルトンパスのうち最も長いものの長さを求めよ。
制約
$2 \leq N \leq 10^5$
$1 \leq A_i \le B_i \leq N$
$1 \leq C_i \leq 10^8$
入力で与えられるグラフは木
入力はすべて整数
考え方
実際に完全グラフを作るのは制約上不可能なので、与えられた木の上で考えることになる。
これは、完全グラフの各辺の長さは木における最短距離、つまりパスの長さであることから元の木で適切な$N-1$本のパスの長さを足し合わせていくと考えれば良い。
ここで適切とは、パスの端点となるのは各頂点1回または2回であるということである。
まず、各辺においてパスに含まれる回数の最大値を考える。
辺を切ったときにできる2つの部分木からそれぞれ1つずつ頂点を選んだとき、これらを端点とするパスのみがその辺を含む。
パスの選び方から、ある部分木から頂点を選ぶのは高々木の大きさの2倍である。
つまり、最大値はその辺で木を切ったときにできる2つの部分木の大きさの小さい方の2倍である。
具体的には大きい方の部分木からはじめて、2つの部分木を交互に行くようにすれば達成できる。
しかし、2つの部分木の大きさが等しいとこれらのパスは$N$本あることになるのでこの場合は別に考える必要がある。
先に2つの部分木の大きさが等しくない時のことを考える。
何本かのパスをある辺が含まれるようにし、かつその回数が最大となるように選んだとする。
この時、具体的な構成方法を見ると分かるように、パスのつながりの端点はともに大きい方の部分木にある。
そこで、各辺において小さい部分木から大きい部分木に向けて矢印を書くことにする。
すると矢印によってたどり着く頂点は、ある辺で切ったときにできる2つの部分木の大きさが等しいものが存在する時はその辺の端点の2つ、そうでなければ1つである。
仮にそうならないとすると、ある頂点から矢印が2本以上出ていることになるが、これは$C > 0$かつ$A > B+C$かつ$A+C < B$が成り立つことになり矛盾する。
後者の場合、矢印の集まる頂点（実は木の重心）を$G$とすると
$G$から出ている辺において、その辺がパスに含まれる回数の最大値の総和は$2(N-1)$である。
しかしそれを達成した時、$G$が一度もパスの端点になっていないので不適である。
そこで、$G$から出ている辺のうち一番短いものを使う回数を1回減らすことを考えると、これは実現可能である。
また、より短い辺を使わないようにすると$G$から出ている辺のうちの1つが使われる回数が減るので、最適でもある。
最後にある辺が等しい大きさの部分木をつないでいる時を考える。
今までの考察から、その辺を使う回数は$N-1$回となるが、他の辺を使う回数は最大を達成できるのでこれが最適である。
ソースコード
マクロ等はこちら
#define PB(a,b) push_back(make_pair(a,b))
const int MC = 100010;
int N;
vector<P2> V[MC]; //辺の集合
int s[MC]; //頂点1を根としたときの部分木の大きさ
int G; //19,21行参照
LL ans;
void dfs(int p , int q){ //pはqの親
bool b = 1; //重心でありうるかのフラグ
s[q] = 1;
for(auto u : V[q]){
if(u.second == p) continue;
dfs(q,u.second);
s[q] += s[u.second];
ans += (LL)2 * u.first * min(s[u.second],N-s[u.second]);
if(s[u.second] * 2 >= N) b = 0;
if(s[u.second] * 2 == N) G = -u.first;
}
if(b && s[q] * 2 > N) G = q;
}
int main(){
scanf("%d" , &N);
repp(i,1,N){
int A,B,C;
scanf("%d%d%d" , &A , &B , &C);
V[A].PB(C,B);
V[B].PB(C,A);
}
dfs(-1,1);
if(G > 0){
int z = 123456789;
for(auto u : V[G]){
z = min(z,u.first);
}
ans -= z;
} else ans += G;
printf("%lld\n" , ans);
return 0;
}解法まとめ
深さ優先探索を用いて各辺の長さとパスに含まれる回数の最大値の積の総和を求める。(17行)
$s[i]=N/2$のものがあれば頂点$i$とその親を結ぶ辺の長さを、そうでなければ重心を求める。(18,19,21行)
後者の場合、重心から出ている辺のうち最小の辺の長さを求め、先に求めた総和から引く。(33-38行)
前者の場合、求めた辺の長さを先に求めた総和から引く（ソースコードで$G$は負になっていることに注意）。(39行)