题解——[ZJOI2007]时态同步（树形结构）

*为何要写DP？，不是摆明的水题吗 *

题面

Description
小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。

在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。

激励电流在导线上的传播是需要花费时间的，对于每条边e，激励电流通过它需要的时间为t
，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小QQ有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？

Input
root + 一棵树

Output

一个整数表示最低次数

in.1
3
1
1 2 1
1 3 3

out.1
2

数据范围与约定

对于100%数据，n<=1e5 ， t<=1e6

思路

主要思路

由于边值只能增不能减，我们考虑自底向上对每个节点 i 进行处理，i 向非 fa 节点连的边一定等长，否则无论如何都不能满足。我们只要对每个节点求出其儿子的 max 值，并更新其他儿子，更新之差的总和就是答案。

细节：
注意dis开 long long
要不断用 dis[] 更新，不能只用该点所连的边权 w[ i ] ，因为儿子节点到其对应的叶节点的距离并不相同

错误代码

void  dfs( int u , int fa ){
	ll sum = 0LL , ma = 0LL , cnt = 0LL ;
	for( int i = head[ u ] ; i ; i = nex[ i ] ){
		if( to[ i ] == fa )continue ;
		dfs( to[ i ] , u ) ;
		sum += (ll)w[ i ] , ma = max( (ll)w[ i ] , ma ) , cnt++ ;
	}
	ans += ma*cnt - sum ;
}

正确写法

void  dfs( int u , int fa ){
	ll sum = 0LL , ma = 0LL ;
	for( int i = head[ u ] ; i ; i = nex[ i ] ){
		if( to[ i ] == fa )continue ;
		dfs( to[ i ] , u ) ;
		ma = max( dis[ to[i] ] + w[ i ] , ma ) ;//统计最大值
	}
	dis[ u ] = ma ; //更新dis[ u ]
	for( int i = head[ u ] ; i ; i = nex[ i ] ){
		if( to[ i ] == fa )continue ;
		ans += dis[ u ] - w[ i ] - dis[ to[ i ] ] ;  //统计贡献
	}
}

完整代码

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 500005 ;
inline int read(){
	int s=0 ; char g=getchar() ; while(g>'9'||g<'0')g=getchar() ; 
	while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
int N , root , to[ MAXN*2 ] , nex[ MAXN*2 ] , head[ MAXN ] , w[ MAXN*2 ] , tot = 1;
ll ans = 0LL , dis[ MAXN ];
void add( int x , int y , int z){
	to[ ++tot ] = y , nex[ tot ] = head[ x ] , w[ tot ] = z , head[ x ] = tot ;
} 
void  dfs( int u , int fa ){
	ll sum = 0LL , ma = 0LL ;
	for( int i = head[ u ] ; i ; i = nex[ i ] ){
		if( to[ i ] == fa )continue ;
		dfs( to[ i ] , u ) ;
		ma = max( dis[ to[i] ] + w[ i ] , ma ) ;
	}
	dis[ u ] = ma ; 
	for( int i = head[ u ] ; i ; i = nex[ i ] ){
		if( to[ i ] == fa )continue ;
		ans += dis[ u ] - w[ i ] - dis[ to[ i ] ] ;  
	}
}
int main(){
	N = read() , root = read() ; int m1 , m2 , m3 ;
	for( int i = 1 ;  i < N ; ++i ){
		m1 = read() , m2 = read() , m3 = read() ;
		add( m1 , m2 , m3 ) , add( m2 , m1 , m3 ) ;
	}
	dfs( root , root ) ;
	cout<<ans ;
	return 0 ;
}