题目传送门
赛后感慨： 大一的我，去参加湘潭大学邀请赛还是比较兴奋的，我知道自己学校的实力并不强，所以并没有抱着能拿奖的心态去的，当时的我对于ACM也只是盲目的热爱，因为这次湘潭大学邀请赛，也让我看到了自己学校与其他学校的真正差距，也明白了自己究竟想要什么；我想要的是能为学校拿奖（也为自己），能让自己足够的强。 比赛期间看着旁边的队气球越来越多，我队的气球却还是两个，当时的心情…。这个题目当时我肯定做不出来，当时我图论一个知识点都没有看过，暑假集训二十多天里，因为自己是负责队里图论方面，也接触了树的直径，所以现在这个题目也可以轻松的解决；今年暑假好好努力准备省赛吧!
思路分析： 我先从1节点搜索到距离最远的直径上的节点node[0]，然后再从node[0]搜索找到距其最远的节点node[1],也就是另一个直径节点，同时更新每一个点到node[0]的距离，再从node[1]进行搜索更新每一个点到直径节点node[1]的距离，然后每个点到直径节点的最大距离进行累加。因直径考虑了两次，故减去一次直径就是最后的答案，三次搜索即可。
AC代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<queue> #include<map> #include<cstdlib> #include<set> #include<list> #include<cmath> using namespace std; #define F(i,n) for(int i=1;i<=n;i++) #define MEM(a,x) memset(a,x,sizeof(a)) typedef long long ll; typedef pair<int,ll>P; const ll INF=-9999999999; //距离初始为负数，并不是求最短路，而是更新更远的距离 const int maxn=100000+10; ll dis[3][maxn]; //存储三次BFS产生的距离，只需要对后两组距离进行选择 int n,m; vector<P>G[maxn]; //存边 bool vis[maxn]; //判断点是否标记过 int node[2]; //存储树的直径两节点 ll MAX; void BFS(int u,int t)//u为搜索的点，t为第几次BFS搜索 { int i; F(i,n) dis[t][i]=INF; //初始化 MEM(vis,false); //初始全部没有标记过 dis[t][u]=0; // queue<int>que; que.push(u); MAX=0; while(!que.empty()) { int x=que.front(); que.pop(); vis[x]=true; //已经标记 for(i=0;i<G[x].size();i++)//更新跟点x的有边的点的距离 { P p=G[x][i]; if(!vis[p.first]&&dis[t][p.first]<dis[t][x]+p.second) //没有标记过 ，并且距离更加远 { dis[t][p.first]=dis[t][x]+p.second; //更新距离 que.push(p.first); //点入队 if(dis[t][p.first]>MAX) //更新最长两点距离 { MAX=dis[t][p.first]; if(t<2) node[t]=p.first; //在t<2时，寻找树的直径节点 } } } } } int main() { while(scanf("%d",&n)==1) { int i,j; F(i,n) G[i].clear(); //清除前数据的边 F(i,n-1) { int x,y; ll len; scanf("%d%d%I64d",&x,&y,&len); G[x].push_back(P(y,len)); G[y].push_back(P(x,len)); //无向图存边 } BFS(1,0); //寻找第一个树的直径节点 BFS(node[0],1); //寻找第二个树的直径节点，并且更新每个点到此节点的距离 BFS(node[1],2); //求每个点到第二个树的直径节点的距离 ll sum=0; F(j,n) { sum+=max(dis[1][j],dis[2][j]); //取每个点到树的直径两节点的最大距离 } printf("%I64d\n",sum-MAX); //因直径考虑了两次，故减去一次直径 } return 0; }