[ZJOI 2007] 时态同步

知识点

树形动态规划、贪心、迭代遍历

解题思路

以激发器S为根，用迭代遍历取得父子顺序。逆序处理节点u，设其各孩子的已同步子树总耗时为h[v]+w，取最大H；将其他分支补到H，差额加入答案，令h[u]=H。

正确性说明

任何同步方案的u到叶时间不能小于最长分支H。对短分支补齐差额至少需要增加相应的传播长度，把差额全部加在u到孩子的入口边上可以一次作用于该分支所有叶子，达到这一最低代价。子树内部已最优同步，逐节点归纳得到全树最少增加量。

易错点

边为无向，须按S重新定根；N可为1；长链不能递归；路径时间和总增加量使用64位。

复杂度

时间O(N)，空间O(N)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,s;cin>>n>>s;vector<vector<pair<int,int>>>g(n+1);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});}vector<int>pa(n+1),order(1,s);for(int i=0;i<(int)order.size();i++){int u=order[i];for(auto[v,w]:g[u])if(v!=pa[u])pa[v]=u,order.push_back(v);}vector<long long>h(n+1);long long ans=0;for(int i=n-1;i>=0;i--){int u=order[i];long long mx=0;for(auto[v,w]:g[u])if(v!=pa[u])mx=max(mx,h[v]+w);for(auto[v,w]:g[u])if(v!=pa[u])ans+=mx-h[v]-w;h[u]=mx;}cout<<ans<<'\n';}