题解：P10974 Accumulation Degree

· · 题解

这不一眼换根 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();
}

\color{grey}{\tiny{\texttt{发现上面的签名是动图了吗？}}}