问题描述
一张包含个节点、
条边的无向连通图，其中，节点从1到
进行编号，每条边的长度均为1。假设从1号节点出发并打算遍历图中所有节点，那么所需要的总路程至少是多少？
解题思路
一共条边，每条边走2次，共
大小的总路程。当不回头的path为最大深度path时，总路程最小。记最大深度值为
，则最小总路程等于
。
程序实现
#include<bits/stdc++.h> //万能头文件，包含了目前C++所包含的所有头文件
using namespace std;
const int MAXN=100001;
vector<vector<int>> vec(MAXN);
int deep;
void dfs(int start,int prev,int w){
for(int i=0;i<vec[start].size();i++){
if(vec[start][i]==prev) continue;
dfs(vec[start][i],start,w+1);
}
deep=max(deep,w);
}
int main(){
int N;
cin>>N;
for(int i=1;i<N;i++){
int x,y;
cin>>x>>y;
vec[x].push_back(y);
vec[y].push_back(x);
}
deep=0;
dfs(1,-1,0);
cout<<2*(N-1)-deep<<endl;
return 0;
}
