AT_abc409_e 题解

题目大意

给定一颗树与其点权、边权，从一个点

u

移动

1

至其相邻点

v

代价为边

(u,v)

的权值

w_{u,v}

，求将所有点权变为

0

的最小代价。

题目分析

首先，显然，从一个点移动

1

至另一个点的最小代价是固定的，为其简单路径的边权总和，则只要不重复走边结果一定是最优的。

其次，我们发现从

u

移动

1

至

v

等价与从

v

移动

-1

至

u

，则任选一点为根，使用树形动态规划，将所有点权移动到根节点即可。

状态转移方程：

f_u = f_u + f_v

。

答案累加：

ans = ans + \lvert f_v \rvert * w_{u,v}

。

可以说是板子题了。

Code

CPP

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const ll inf = LONG_LONG_MAX, N = 100050;

ll n, u, v, c, ans = 0; 
ll arr[N]; 
vector<PII> e[N];

void dfs(ll now, ll fa){
	for(PII i : e[now]){
		int y = i.first, w = i.second;
		if(y == fa) continue;
		dfs(y, now);
		ans += w * abs(arr[y]);
		arr[now] += arr[y];
	}
}

int main(){
	scanf("%lld", &n);
	for(int i = 1; i <= n; i ++)
		scanf("%lld", &arr[i]);
	for(int i = 1; i < n; i ++){
		scanf("%lld%lld%lld", &u, &v, &c);
		e[u].push_back({v, c});
		e[v].push_back({u, c});
	}
	dfs(1, -1);
	printf("%lld\n", ans);
	return 0;
}

文章操作

题目大意

题目分析

Code

相关推荐

评论

AT_abc409_e 题解