树的直径-蓝桥杯大臣的旅费

首先从u dfs找到最远点v ，然后从v开始，dfs找到的最远点一定是树的直径

证明：
如果u->v 和树的直径没有公共点，则可以从树的直径终点到u引一条边，树直径变长了，矛盾
假设交点为k，那么k->v (或者就是v本身) 一定是树直径的一部分，（最优子结构）

这样就证明了v一定在树的直径的端点处，（为什么是端点，因为u->v是最远的，一定是叶子节点）

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6  
 7 const int maxn = 1e6 + 5;
 8 int n, max_dis = -1, vis[maxn], start;
 9 vector<int> g[maxn];
10 vector<int> e[maxn];
11  
12 int cal(int x)
13 {
14     int res = 0;
15     for(int i=1;i<=x;++i)res+=(i+10);
16     return res;
17 }
18 
19 void dfs(int u,int sum)
20 {
21     vis[u] = 1;
22     if(sum>max_dis)
23     {
24         max_dis = sum;
25         start = u;
26     }
27     for(int i=0;i<g[u].size();++i)
28     {
29         if(!vis[g[u][i]]) dfs(g[u][i],sum+e[u][i]);
30     }
31 }
32  
33 int main()
34 {
35     freopen("input.txt","r",stdin);
36     cin>>n;
37     int u,v,k;
38     for (int i=0;i<n-1;++i)
39     {
40         cin>>u>>v>>k;
41         g[u-1].push_back(v-1);
42         g[v-1].push_back(u-1);
43         e[u-1].push_back(k);
44         e[v-1].push_back(k);
45     }
46     dfs(0,0);
47     //任意取一个点寻找最远的结点start
48     max_dis=-1;
49     memset(vis,0,sizeof(vis));
50     dfs(start,0);//从start开始求解树的直径
51     //重置深搜时使用的变量
52     cout<<cal(max_dis)<<endl;
53     return 0;
54 }

树的直径-蓝桥杯大臣的旅费

推荐阅读