题目描述
换根dp,推荐洛谷P2986,首先我们总结一下换根dp的特点。当题目中根节点不明确需要你以每一个点为根找到最优解时,如果每一个点都去做一次dfs那么时间复杂度就是O(n^2),超过1e4的数据一定会超时,那么此时如果能够有一个递推关系用某一个节点的信息在O(1)的时间复杂度内就能推算其他所有点的信息,此时就需要用到换根dp
总的来说,换根dp就是需要两次dfs,第一次预处理以某点为根的信息(son->fa),第二次递推关系(fa->son)
算法1
(dfs) $O(n)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using i64=long long;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin>>n;
std::vector<std::pair<int,int>>adj[n+1];
for(int i=1;i<n;i++){
int u,v,w;
std::cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
std::vector<int>f1(n+1),f2(n+1),g(n+1);
std::vector<int>s(n+1);
std::function<void(int,int)>dfs1=[&](int u,int fa)->void{
for(auto t:adj[u]){
int v=t.first,w=t.second;
if(v==fa){
continue;
}
dfs1(v,u);
if(f1[v]+w>=f1[u]){
f2[u]=f1[u],f1[u]=f1[v]+w;
s[u]=v;
}
else if(f1[v]+w>f2[u]){
f2[u]=f1[v]+w;
}
}
};
std::function<void(int,int)>dfs2=[&](int u,int fa)->void{
for(auto t:adj[u]){
int v=t.first,w=t.second;
if(v==fa){
continue;
}
if(s[u]==v){
g[v]=w+std::max(g[u],f2[u]);
}
else{
g[v]=w+std::max(g[u],f1[u]);
}
dfs2(v,u);
}
};
dfs1(1,0);
dfs2(1,0);
int ans=2e9;
for(int i=1;i<=n;i++){
ans=std::min(ans,std::max(f1[i],g[i]));
}
std::cout<<ans<<"\n";
}