Solution of ZJOI2007-时态同步

树形Dp:

设: Dp[i]表示从第i个节点发出激励电流达到时态同步最少需要操作的次数

num[i]表示从第i个节点发出激励电流,Dp[i]最少时，从第i个节点到达叶子节点需要的时间最大值 ;

可得: $num[i]=max\{num[j]+edge(i,j)|fa[j]=i\}$ $Dp={\sum }_j^{fa[j]=i}Dp[j]+{\sum }_j^{fa[j]=i}num[i]-num[j]-edge(i,j)$

直接暴力转移即可,用类似Dfs的方法实现

demo:

#include<iostream> #include<cstdio> #include<algorithm> #define MAXN 500005 #define MAXM 500005 #define loop(X) for(int i = head[(X)] ; i ; i = Next[i]) using namespace std ; int edge[MAXM] , ver[MAXM] , Next[MAXM] , head[MAXN] , maxv[MAXN] ; int tot , N , S ; long long ans ; void add(int x,int y,int z){ edge[++tot] = z , ver[tot] = y , Next[tot] = head[x] ,head[x] = tot ; } void dfs(int x,int fa){ loop(x) if(ver[i] != fa) dfs(ver[i] , x) ; loop(x) if(ver[i] != fa) maxv[x] = max(maxv[x] , edge[i]) ; loop(x) if(ver[i] != fa) ans+=(maxv[x] - edge[i]) ; loop(fa) if(ver[i] == x) edge[i] += maxv[x] ; } int main(){ scanf("%d%d",&N,&S) ; for(int i = 1 ; i < N ; ++i){ int x , y , z ; scanf("%d%d%d",&x,&y,&z) ; add(x,y,z) , add(y,x,z) ; } dfs(S,0) ; printf("%lld\n",ans) ; }