树上游走最优策略问题：Cf1725J

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133622359

https://codeforces.com/contest/1725/problem/J

首先要转化题目

发现题目本质是什么

不用回去 = 少走一条路径

传送 = 少走另一条路径

一开始猜的结论是这样
在这里插入图片描述

但这并不完整

传送本质是让我们把某些路径少走一遍

考虑这种情况，交于1点

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 200010
//#define M
//#define mo
struct node {
	int w, x; 
	bool operator < (const node &A) const {
		return w<A.w; 
	}
	bool operator > (const node &A) const {
		return w>A.w; 
	}
}mx1[N], mx2[N], mx3[N], mx4[N], s1[N], s2[N];
struct Node {
	int y, z; 
};
int n, m, i, j, k, T; 
int u, v, w, ans, sum, d[N]; 
vector<Node>G[N]; 

void work(node y, int x) {
	if(y>mx1[x]) mx4[x]=mx3[x], mx3[x]=mx2[x], mx2[x]=mx1[x], mx1[x]=y; 
	else if(y>mx2[x]) mx4[x]=mx3[x], mx3[x]=mx2[x], mx2[x]=y; 
	else if(y>mx3[x]) mx4[x]=mx3[x], mx3[x]=y; 
	else if(y>mx4[x]) mx4[x]=y; 
}

void work2(node y, int x) {
	if(y>s1[x]) s2[x]=s1[x], s1[x]=y; 
	else if(y>s2[x]) s2[x]=y; 
}

void dfs1(int x, int fa) {
	for(auto t : G[x]) {
		int y=t.y, z=t.z; 
		if(y==fa) continue; 
		dfs1(y, x); 
		work({mx1[y].w+z, y}, x); 
		work2({max(s1[y].w, d[y]), x}, x); 
		d[x]=max(d[x], d[y]); 
	}
	d[x]=max(d[x], mx1[x].w+mx2[x].w); //子树内最大直径 
}

void dfs2(int x, int fa) {
	for(auto t : G[x]) {
		int y = t.y, z = t.z; 
		if(y == fa) continue; 
		node f; f.x=x; f.w=z; 
		if(mx1[x].x==y) f.w+=mx2[x].w; 
		else f.w+=mx1[x].w; 
//		pr
		work(f, y); 
		dfs2(y, x); 
	}
	ans=max(ans, mx1[x].w+mx2[x].w+mx3[x].w+mx4[x].w); 
//	printf("%lld : %lld %lld %lld %lld\n", x, mx1[x].w, mx2[x].w, mx3[x].w, mx4[x].w); 
}

void Choose_Not(int &s, int x, int y) {
	if(mx1[x].x==y) s+=mx2[x].w+mx3[x].w; 
	else if(mx2[x].x==y) s+=mx1[x].w+mx3[x].w; 
	else s+=mx1[x].w+mx2[x].w; 
}

void dfs3(int x, int fa, int D) { //D：非x子树的最大直径 
	for(auto t : G[x])  {
		int y = t.y, z = t.z; 
		if(y == fa) continue; 
		int newd=0; 
		Choose_Not(newd, x, y); 
		newd=max(newd, D); 
		if(s1[x].x==y) newd=max(newd, s1[x].w); 
		else newd=max(newd, s2[x].w); 
//		printf("%d - > %d %lld %lld %lld\n", x, y, 2*z, d[y], newd); 
		ans=max(ans, 2*z+d[y]+newd); 
		dfs3(y, x, newd); 
	}
}


signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); 
	for(i=1; i<n; ++i) {
		u=read(); v=read(); w=read(); 
		sum+=2*w; 
		G[u].pb({v, w}); G[v].pb({u, w}); 
	}
	dfs1(1, 0); dfs2(1, 0); dfs3(1, 0, 0); 
//	printf("%lld\n", ans); 
	printf("%lld", sum-ans); 
	return 0;
}