where
錦囊(?)
於討論串得到，只要以樹直徑中心點為根即可。
思考
要合併成一條樹鍊，一定會先變成他的樹直徑，之後再對折。
以及，以樹直徑中心為根的話，那麼兩邊鏈必定等長，而其下的各子樹的深度一定會再樹直徑砍半以內。
一個greedy的概念（？），其實是我還沒想出證明。
那如果直徑是奇數呢？
以中間那兩點來看，會發現不管從哪邊跑，底下的子樹都能好好被檢查合併到，那麼只要從隨便一個點開始就可以了。
樹直徑中心要怎麼找呢？
於樹直徑兩端到另一端標記上經過的邊數，會發現中心為標記相同或者標記相差1以內之點。
Code 大綱
- dfs找到最深的點
- 由該最深的點再一次dfs找到另一個最深的點，沿途標記深度
- 反過來由上一個找到的點dfs、標記深度，同時檢查是否為中心
- 由中心dfs下去，回傳該鍊的節點數，確認是否能成鏈，否則為-1
- 若能成鏈，從中心的子樹們得到總鏈的邊長，繼續對折
Code_乖乖合併版
#include <bits/stdc++.h>
using namespace std;
int T, N, M, L, tag[200005];
//pair<鏈的節點數, 連接的節點為>
vector<pair<int, int> > node[200005];
void ini(void){
int i, j, k;
scanf("%d", &N);
for(i = 1; i < N; i++){
scanf("%d %d", &j, &k);
//鏈的節點數初始為零，日後於連接parent的會被sort在第零個（根除外）
node[j].push_back(make_pair(0, k) );
node[k].push_back(make_pair(0, j) );
}
}
int dfs(int x, int p, int first){
if(first){
//這個dfs用來回傳最深的點，並沿途標記
int j, k = x;
tag[x] = tag[p] + 1;
for(int i = 0; i < node[x].size(); i++){
if(node[x][i].second != p){
j = dfs(node[x][i].second, x, first);
if(tag[j] > tag[k]) k = j;
}
}
return k;
}else{
//沿途標記、確認是否為中心，回傳中心點
int j, k = 0;
//確認是否為中心
if(x != p && tag[x] - 1 <= tag[p] + 1
&& tag[x] + 1 >= tag[p] + 1)
return x;
tag[x] = tag[p] + 1;
for(int i = 0; i < node[x].size(); i++){
if(node[x][i].second != p){
j = dfs(node[x][i].second, x, first);
if(!k && j) k = j;
}
}
return k;
}
}
int combine(int x, int p){
//合併，回傳鏈的節點數，若無法成鏈，則直接回傳-1
int i, j, k = 0;
for(i = 0; i < node[x].size(); i++){
if(node[x][i].second != p){
j = combine(node[x][i].second, x);
if(j < 0) return -1;
//將鏈的長度標於該點上
node[x][i].first = j;
//保留鏈最長，若可成鏈，那這子樹的總長就靠它惹
if(j > k) k = j;
}
}
sort(node[x].begin(), node[x].end());
//如果不是根節點，則跳過第一個
if(x != p) i = 2;
else i = 1;
for(; i < node[x].size(); i++){
//於非根節點的子樹，鏈必定只剩一條，若非，則無法成鏈
if(node[x][i].first == node[x][i - 1].first){
node[x][i - 1].first = -1;
}else if(x != p){
return -1;
}
}
//加上自己
return k + 1;
}
void sol(void){
int c = dfs(1, 1, 1);
//初始，因一進去就會被加一個惹
tag[c] = -1;
c = dfs(c, c, 1);
tag[c] = -1;
c = dfs(c, c, 0);
int ans = combine(c, c);
if(ans < 0){
printf("-1\n");
}else{
//記錄以中心為根的剩餘子樹的數量，好判斷是否超過2（不成鏈）
int j = 0;
//記錄總鏈之鍊長（邊數），因不包含中心本身
ans = 0;
for(int i = 0; i < node[c].size(); i++){
//-1為已合併
if(node[c][i].first > 0){
++j;
ans += node[c][i].first;
}
}
if(j > 2) printf("-1\n");
else{
//繼續合併
while(!(ans & 1)) ans >>= 1;
printf("%d\n", ans);
}
}
}
int main(void){
int i, j;
ini();
sol();
}
Code_用map喇
#include <bits/stdc++.h>
using namespace std;
int T, N, M, L, tag[200005];
vector<int> node[200005];
void ini(void){
int i, j, k;
scanf("%d", &N);
for(i = 1; i < N; i++){
scanf("%d %d", &j, &k);
node[j].push_back(k);
node[k].push_back(j);
}
}
int dfs(int x, int p, int first){
if(first){
int j, k = x;
tag[x] = tag[p] + 1;
for(int i = 0; i < node[x].size(); i++){
if(node[x][i] != p){
j = dfs(node[x][i], x, first);
if(tag[j] > tag[k]) k = j;
}
}
return k;
}else{
int j, k = 0;
if(x != p && tag[x] - 1 <= tag[p] + 1
&& tag[x] + 1 >= tag[p] + 1)
return x;
tag[x] = tag[p] + 1;
for(int i = 0; i < node[x].size(); i++){
if(node[x][i] != p){
j = dfs(node[x][i], x, first);
if(!k && j) k = j;
}
}
return k;
}
}
//上面只差在node而已
int combine(int x, int p){
int i, j, k = 0;
map<int, int> ma;
map<int, int>::iterator ite;
for(i = 0; i < node[x].size(); i++){
if(node[x][i] != p){
j = combine(node[x][i], x);
if(j < 0) return -1;
ma[j]++;
}
}
for(ite = ma.begin(), j = 0; ite != ma.end(); ++ite){
j++;
k += ite->first;
}
if(x != p && j > 1) return -1;
if(x == p && j > 2) return -1;
return k + 1;
}
void sol(void){
int c = dfs(1, 1, 1);
tag[c] = -1;
c = dfs(c, c, 1);
tag[c] = -1;
c = dfs(c, c, 0);
int ans = combine(c, c); //回傳的是鏈節點數
if(ans < 0){
printf("-1\n");
}else{
--ans;
while(!(ans & 1)) ans >>= 1;
printf("%d\n", ans);
}
}
int main(void){
int i, j;
ini();
sol();
}
後記
會有pair<int, int>是因為在寫的時候想說，最後面的總鏈長需要再一次dfs，那麼就會需要知道哪個是被合併掉的。Zz
寫到那裡才發現不用。QwQ
也不用認真去合併惹。
子樹內各個小孩的鏈長必定得一樣。
好的，寫到這我又發現，不用用map喇。OAO”
總之我丟了三個版本的code，其中有趣的是，第二版是pair<int, int>和map，第三版是int和map。
但是第三版的比較慢。
這真的很傑克。