营销网站的建设流程,佛山建设网站制作,做某健身房网站的设计与实现,太原网站建设注意Bob in Wonderland
题意#xff1a;
一棵树#xff0c;问最少移动多少次边可以使其变成一个链#xff1f; 移动是指#xff1a;从原位置拆下并连到新位置#xff0c;这样算一次
题解#xff1a;
错误思路
我一开始在想既然求最少移动次数#xff0c;那我们就尽可能…Bob in Wonderland
题意
一棵树问最少移动多少次边可以使其变成一个链 移动是指从原位置拆下并连到新位置这样算一次
题解
错误思路
我一开始在想既然求最少移动次数那我们就尽可能在原本的就存在的链的基础上进行修改也就是先找树中最长的链即树的直径然后看这条链上有多少子链相连拆下来再连上即可所以先跑两边dfs求出最长直径并记录直径上的点然后依次查看直径上的点的度数是否大于2如果大于2就说明除了前后两个点还有其他点相连注意如果7连在6上然后6连在直径上那6和7是算一个整体的所以只需要查看直径点的度数即可
正确思路
但是。。代码就是wa。。。感觉是两边dfs不对 我也很懵逼后来又想了想其实完全没这么复杂因为没有必要先求直径我们直接求所有点的度数然后查看度数是否大于等于2并累加即可 而且如果链的上面存在链怎么办也就是7连着6,6连着5,5连着直径上一点但是6还连接着其他链这样我们只查看直径上的点就不对了应该是查看所有度数大于2的点 先求树的直径纯属画蛇添足因为如果所有点组成链那么所有点的度数必然小于等于2两端等于1中间等于2,所以直接查看所有点度数就行
代码
#includebits/stdc.h
using namespace std;
const int maxn6e59;
vectorintG[maxn];
int main()
{int n;cinn;for(int i1;in;i){int x,y;cinxy;G[x].push_back(y);G[y].push_back(x);}int sum0;for(int i1;in;i){int wG[i].size()-2;if(w0){sumw; }}coutsumendl;return 0;
}
