PREV-9(大臣的旅费)
题目给定n个城市，n-1条路，显然题意是要在一棵树上求任意两点距离的最大值
/----------------------------------接下来两段可忽略------------------------------------/
题目没给定n的范围，所以贸然用Floyd来求两点间的最短距离是不可取的
Floyd的时间复杂度为O(n^3),n随便取大一点就很容易超时
再者，这题不需要求两点间的最短距离，因为任意两点间的距离都是固定的(这个可以自己想想)
在一棵树上求两点的距离，或许会想到两点的最近公共祖先，用算法LCA来求
求任意两点的最近祖先，得查询C(n,2)次，时间复杂度为O(n^2) 这样仍然不能保证全过
听说有一种将最近公共祖先转换成RMQ问题的时间复杂度为O(nlogn)的在线算法(可自行度娘)
当然这题也不应该用关于两点的最近公共祖先的算法来求，在n未知的情况下，时间复杂度还是太高了
/----------------------------------以下才是关键------------------------------------/
题目只要求最大值，完全可以用树形动归来，dfs遍历一遍所有边就好，时间复杂度O(n)
任意取一点作为根结点，dfs深搜，从叶子节点向上动归
DP[i]维护以i为根节点的子树中节点i到叶子节点的最长距离
MAX[i]维护以i为根节点的子树中经过节点i的最大两点间距离 答案自然是MAX[]中的最大值
<C++> Code
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define MAXN 100010 //不知n为多大，随便定义了个，可以定义更大，也可以想想用vector容器 5 #define LL long long 6 7 int n; 8 LL Dp[MAXN],Max[MAXN],ans;//全区变量自动初始化为0 9 10 //链式前向星 11 int head[MAXN],m=1;//因为head[]中元素都为0，所以m从1计数就不用初始化head[]了 12 struct Edge{ 13 int to,next,w; 14 }e[MAXN]; 15 16 //链式前向星添加边 17 void add_edge(int u,int v,int w){ 18 e[m].to = v; 19 e[m].w = w; 20 e[m].next = head[u]; 21 head[u] = m++; 22 } 23 24 25 bool f[MAXN];//标记节点是否已被访问过 26 void dfs(int s){ 27 int k = head[s]; 28 while(k > 0){ 29 int t = e[k].to;//t为s的孩子节点 30 if(!f[t]){ 31 f[t] = true; 32 dfs(t); 33 Max[s] = max(Max[s] , Dp[s] + Dp[t]+e[k].w);//以s为根节点的子树中 经过s的最大两点间距离 34 Dp[s] = max(Dp[s] , Dp[t]+e[k].w);//s到叶子节点的最长距离 35 } 36 k = e[k].next; 37 } 38 ans=max(ans,Max[s]); 39 } 40 41 42 void work(){ 43 f[1]=true; 44 dfs(1);//以节点1为根节点深搜 ，深搜前标记1被访问 45 printf("%I64d\n",ans*(21+ans)/2); 46 } 47 48 49 void init(){ 50 scanf("%d",&n); 51 int p,q,d; 52 for(int i = 1 ; i < n ; i++){ 53 scanf("%d%d%d",&p,&q,&d); 54 add_edge(p,q,d); 55 add_edge(q,p,d);//双向边建图，方便dfs 56 } 57 } 58 59 60 int main() 61 { 62 init(); 63 work(); 64 return 0; 65 }
蓝桥杯官网练习系统历届真题详解,布布扣,bubuko.com
原文：http://www.cnblogs.com/cshhr/p/3584271.html
