题干：
链接：https://ac.nowcoder.com/acm/contest/369/C
来源：牛客网
小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度
欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次
输入描述:
第一行一个数 n ，表示节点个数
接下来 n-1 行，每行三个整数 u,v,w，表示有一条 u 到 v 边权为 w 的无向边
保证数据是一棵树
输出描述:
一行一个整数，表示答案
示例1
输入
4 1 2 1 1 3 1 1 4 2
输出
5
说明
一种可能的方案为复制 <1,2,1> 这条边一次，欧拉路为4->1->2->1->3
备注:
1≤n≤2×1051≤n≤2×105
1≤ui,vi≤n1≤ui,vi≤n
1≤wi≤1041≤wi≤104
解题报告：
思维题，不难发现选择树的直径，剩下的挂到链上，这样一定是最优解。
AC代码：
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;
const int MAX = 6e5 + 5 ;
const int INF = 0x3f3f3f3f;
struct Node {
int to;
int w;
int ne;
} e[MAX];
struct point {
int pos,c;
point(){}
point(int pos,int c):pos(pos),c(c){}
};
int n;
int head[MAX];
int cnt = 0 ;
bool vis[MAX];
void init() {
cnt = 0;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w) {
e[cnt].to = v;
e[cnt].w = w;
e[cnt].ne = head[u];
head[u] = cnt;
cnt++;
}
int bfs(int x,int &w) {
queue <point> q;
int maxx = 0;
int retp = x ;//返回的点坐标
memset(vis,0,sizeof(vis) );
q.push(point(x,0));vis[x] = 1;
point now;
while(q.size() ) {
point cur = q.front();
q.pop();
for(int i = head[cur.pos]; i!=-1; i=e[i].ne) {
if(vis[e[i].to]) continue;
vis[e[i].to] = 1;
now.pos = e[i].to;
now.c = cur.c + e[i].w;
if(now.c>maxx) {
maxx = now.c;
retp = now.pos;
}
q.push(now);
}
//w = maxx;
}
w = maxx;
return retp;
}
int main()
{
cin>>n;
init();
int u,v,w;
ll sum = 0;
for(int i = 1; i<=n-1; i++) {
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
sum += w;
}
int ans1 = 0,ans2 = 0;
u = bfs(1,ans1);
v = bfs(u,ans2);
//printf("ans2 = %d\n",ans2);
printf("%lld\n",1LL*ans2 + (sum-ans2)*2);
return 0 ;
}
/*
9
1 8 1
1 2 2
2 7 3
2 3 1
3 5 3
3 4 10
4 9 4
5 6 2
*/
京公网安备 11010502036488号