自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 23:03:04，当前版本为作者最后更新于2024-09-04 18:18:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这不一眼换根 DP，然后我尝试不用编译器一遍过（也许算成功吧？3 次 CE、1 次 RE），感觉没难度。别被蓝题吓到了，其实挺简单的。

考虑下图（鸣谢 Graph Editor 生成图片）：

显然，$ans_A=c+d+\min\{b,e+f\},ans_B=\min\{b,c+d\}+e+f$。

暴力做法很容易想到：枚举根节点，对于每个根节点，DFS 计算出其对应的结果，取所有结果的最大值作为答案即可。但是时间复杂度为 $\Theta(n^2)$，肯定会超时，思考如何优化。

注意到，计算完 $ans_A$ 后计算 $ans_B$ 时，其余部分点对答案的贡献被重复查找了。着虽然对答案的正确性没有影响，但是造成了极大的事件浪费。

经过分析得出，$ans_B=ans'_B+\min\{b,ans_A-\min\{b,ans'_B\}\}$（$ans'_X$ 表示以上一个节点为根时这个节点不考虑其父边的影响对答案的贡献，下同；这里一定要自己对着图分析一下，还是比较显然的），可以类比出其它的点转移方程。

注意到 $A$ 节点不是叶子节点，那我们再考虑一下如何从叶子节点 $C$ 转移到节点 $A$：$ans_A=ans'_C+c$，因为如果当前根节点只有一个子，那么换根后这个节点的流量也要被新根节点统计。

就完了，时间复杂度为 $\Theta(n)$。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200000+9,inf=0x3f3f3f3f3f3f3f3fLL;
vector<vector<pair<int,int>>>g;
int n,dp[maxn],ans; 
inline int dfs1(const int u,const int fa){
	for(const auto[v,w]:g[u])if(v!=fa)dp[u]+=min(dfs1(v,u),w);
	return dp[u]==0?inf:dp[u];
}
inline void dfs2(const int u,const int fa,const int sum){
	ans=max(ans,sum);
	for(const auto[v,w]:g[u])if(v!=fa){
		if(g[u].size()==1)dfs2(v,u,dp[v]+w);
		else dfs2(v,u,dp[v]+min(sum-min(dp[v],w),w)); 
	}
} 
signed main(){
	static int T=-1;
	if(T==-1){
		ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
		cin>>T;
	}
    if(T--==0)return 0;
	cin>>n,ans=0,g.resize(n+9),g.clear(),memset(dp,0,sizeof dp);
	for(int i=1,u,v,w;i<n;i++)cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w}); 
	dfs1(1,-1),dfs2(1,-1,dp[1]);
	cout<<ans<<'\n';
	main();
}

• UPD. 2024 年 12 月 13 日进行订正，发现之前写的内容出现了不少错误，而作者本人由于已经 AFO 了一个季度，没有怎么接触 OI 导致也一时看不懂自己写的题解（诚挚地向之前阅读本提题解的同学道歉，还是写的太烂了）。如果还有错误希望能得到指出！