Bob in Wonderland

題意：

一棵樹，問最少移動(dòng)多少次邊可以使其變成一個(gè)鏈？
移動(dòng)是指：從原位置拆下并連到新位置，這樣算一次

題解：

錯(cuò)誤思路

我一開始在想既然求最少移動(dòng)次數(shù)，那我們就盡可能在原本的就存在的鏈的基礎(chǔ)上進(jìn)行修改，也就是先找樹中最長的鏈（即樹的直徑），然后看這條鏈上有多少子鏈相連，拆下來再連上即可，所以先跑兩邊dfs，求出最長直徑，并記錄直徑上的點(diǎn)，然后依次查看直徑上的點(diǎn)的度數(shù)是否大于2，如果大于2就說明除了前后兩個(gè)點(diǎn)，還有其他點(diǎn)相連，注意如果7連在6上，然后6連在直徑上，那6和7是算一個(gè)整體的，所以只需要查看直徑點(diǎn)的度數(shù)即可

正確思路

但是。。代碼就是wa。。。感覺是兩邊dfs不對(duì)？？？
我也很懵逼，后來又想了想，其實(shí)完全沒這么復(fù)雜，因?yàn)闆]有必要先求直徑，我們直接求所有點(diǎn)的度數(shù)，然后查看度數(shù)是否大于等于2，并累加即可
而且，如果鏈的上面存在鏈怎么辦？也就是7連著6,6連著5,5連著直徑上一點(diǎn)，但是6還連接著其他鏈，這樣我們只查看直徑上的點(diǎn)就不對(duì)了，應(yīng)該是查看所有度數(shù)大于2的點(diǎn)
先求樹的直徑純屬畫蛇添足，因?yàn)槿绻悬c(diǎn)組成鏈，那么所有點(diǎn)的度數(shù)必然小于等于2（兩端等于1，中間等于2）,所以直接查看所有點(diǎn)度數(shù)就行

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=6e5+9; vector<int>G[maxn]; int main() {int n;cin>>n;for(int i=1;i<n;i++){int x,y;cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}int sum=0;for(int i=1;i<=n;i++){int w=G[i].size()-2;if(w>0){sum+=w; }}cout<<sum<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的2020牛客国庆集训派对day1 C. Bob in Wonderland的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。