P1131 [ZJOI2007]时态同步

P1131 [ZJOI2007]时态同步

Meaning

考虑边带权的树，我们每次操作可以使得一条边的权值加 1，求将每个叶子结点的深度相同最少需要的操作次数。

Sol

树形 dp 经典题。我们令 $dp_{i}$ 表示使得以 $i$ 为根的子树内深度相同的最少操作次数，同时记录下以 $i$ 为根的子树内深度的最大值 $f_u$（因为我们最多使得该子树内每个叶子结点的深度为其最大值）。

那么易知 dp 转移方程

$dp_u = \sum_{v\in edge} dp_v + f_u - f_v$

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=5e5+1e1;
const lint INF=1e18+1e9;

struct Edge{
	int nxt,to,w;
}e[MAXN<<1];
lint dep[MAXN],dp[MAXN];
int head[MAXN],fa[MAXN],n,s,tot;

void Addedge(int u,int v,int w){
	e[++tot]=(Edge){head[u],v,w};
	head[u]=tot;
	return;
}

void Dfs(int u,int depth){
	dep[u]=depth;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(fa[u]==v) continue;
		fa[v]=u,Dfs(v,depth+e[i].w);
		dp[u]+=dp[v],dep[u]=max(dep[v],dep[u]);
	}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(fa[u]!=v) dp[u]+=dep[u]-dep[v];
	}
	return;
}

int main(void){

	scanf("%d%d",&n,&s);
	for(int i=1;i<n;i++){
		int u=readint,v=readint,w=readint;
		Addedge(u,v,w),Addedge(v,u,w);
	}
	Dfs(s,0);
	printf("%lld\n",dp[s]);

	return 0;
}