删边（delete）

题目

题目描述

给你一棵n个结点的树，每个结点有一个权值，删除一条边的费用为该边连接的两个子树中结点权值最大值之和。现要删除树中的所有边，删除边的顺序可以任意设定，请计算出所有方案中的最小花费。

输入格式

输入文件名为 delete.in。

第一行包含整数n，表示结点数。结点用从1到n表示。

第二行包含n个整数ti(1≤ti≤109)。数字ti表示结点i的权值。

接下来n−1行，每行包含两个整数x和y(1≤x,y≤n)，表示结点x和结点y直接相连。

输出格式

输出文件名为 delete.out。

输出最小花费。

题解

题目大意：有一棵树，删去一条边的代价是这条边两端子树里各自权值最大值之和，安排删边顺序使得代价最小，输出最小代价

一道结论题，没什么好说的

\(ans=\sum t_{i}-\max \left\{t_{i}\right\}+\sum \max \left(t_{x_{i}}, t_{y_{i}}\right)\)

证明自行思考

Code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

ll n,x,y,ans,mx,c[100001];

int main()

{

	freopen("delete.in","r",stdin);

	freopen("delete.out","w",stdout);

	scanf("%lld",&n);

	for (int i=1;i<=n;++i)

		scanf("%lld",&c[i]),ans+=c[i],mx=max(mx,c[i]);

	for (int i=1;i<n;++i)

	{

		scanf("%lld%lld",&x,&y);

		ans+=max(c[x],c[y]);

	}

	printf("%lld\n",ans-mx);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

【2020.11.30提高组模拟】删边(delete)

删边（delete）

题目

题目描述

输入格式

输出格式

题解

Code

最新文章

热门文章