, seniors题目链接：?id=1849题目大意：有两个人从同一点出发，遍历一棵树的所有边，每个边有个权值，求遍历的最小代价，题目分析：答案就是所有边权值乘2减去直径，这里不证了，证明的话，简单想就是两个人要走的公共路最长，除了公共路其他部分肯定都走了两次，因为是树，两点间只有唯一的路，所以最长的那条路我不走重复必然就是最小代价了，树上最长链就是树的直径关于怎么求直径，这里也不证了记个结论，两种方法，一是两次dfs，第一次任意找一个点搜索从它开始能走到的最远的点，那个点必然是树的直径的一个端点，，再从这个点开始dfs一下，就搜出了整棵树，二是树形dp的方法，对于任意一个点，搜索其两个能延伸最远和次远的儿子，把两个距离相加再加上两儿子到父亲的距离再取最大就是树的直径，这个很好证，两儿子肯定不在一条延伸路径上，画个图看的更清楚两次DFS:#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;int const MAX = 100005;int n, s, cnt;int dis[MAX], head[MAX];struct EGDE{int v, w, next; }e[MAX];void Add(int u, int v, int w){e[cnt].v = v;e[cnt].w = w;e[cnt].next = head[u];head[u] = cnt++;}void DFS(int u, int fa, int d){for(int i = head[u]; i != -1; i = e[i].next){int v = e[i].v;int w = e[i].w;if(v != fa){dis[v] = w + d;DFS(v, u, w + d);}}return;}int main(){cnt = 0;int sum = 0;scanf("%d %d", &n, &s);memset(head, -1, sizeof(head));memset(dis, 0, sizeof(dis));for(int i = 0; i < n – 1; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);Add(u, v, w);Add(v, u, w);sum += 2 * w;}dis[s] = 0;DFS(s, -1, 0);int o, ma = -1;for(int i = 1; i <= n; i++){if(dis[i] > ma){ma = dis[i];o = i;}}dis[o] = 0;DFS(o, -1, 0);ma = -1;for(int i = 1; i <= n; i++)if(dis[i] > ma)ma = dis[i];printf("%d\n", sum – ma);}树形dp：#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 100005;int head[MAX], dp[MAX][2];int n, s, cnt, ans;struct EDGE{int v, w, next;}e[MAX];void Add(int u, int v, int w){e[cnt].v = v;e[cnt].w = w;e[cnt].next = head[u];head[u] = cnt ++;}void DFS(int u, int fa){dp[u][0] = dp[u][1] = 0;for(int i = head[u]; i != -1; i = e[i].next){int v = e[i].v;int w = e[i].w;if(v != fa){DFS(v, u);if(dp[u][0] < dp[v][0] + w){int tmp = dp[u][0];dp[u][0] = dp[v][0] + w;dp[u][1] = tmp;}else if(dp[u][1] < dp[v][0] + w)dp[u][1] = dp[v][0] + w;}}ans = max(ans, dp[u][1] + dp[u][0]);return;}int main(){cnt = 0;ans = 0;memset(head, -1, sizeof(head));scanf("%d %d", &n, &s);int sum = 0;for(int i = 0; i < n – 1; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);Add(u, v, w);Add(v, u, w);sum += 2 * w;}DFS(s, -1);printf("%d\n", sum – ans);}
依赖别人的人等于折断了自己的翅膀，永远也体会不到飞翔的快乐。
