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

本文主要是介绍树上游走最优策略问题：Cf1725J，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

首先要转化题目

发现题目本质是什么

不用回去 = 少走一条路径

传送 = 少走另一条路径

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

但这并不完整

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

考虑这种情况，交于1点

在这里插入图片描述

#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; 
//		prwork(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;
}