首页 > Decrement on the Tree
开通博客写题解
头像 TitanZhang
发表于 2020-08-11 13:36:21
题目大意 有一棵包含n个顶点（n-1条边）的带边权的树，每次都可以选择两个不同的顶点，将这条链上每个边权值减去1。要使所有边权值为零，最小操作数是多少？还需要支持边权的修改：将第p个边的权重更改为w，每次修改后都要输出答案。 解题思路 没有图示，我很抱歉！我会尽量清楚地叙述一下这个做法的原理。（刚才 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 梁好问tanget90°
发表于 2020-08-11 15:53:40
原题链接：https://ac.nowcoder.com/acm/contest/5675/C 题目描述 有一颗有n个顶点和n-1条边的树，每条边都有非负的权值，每次可以选择两个不同的顶点u,v，并将连接这两个顶点的边的权值减去一。请问最少要操作多少次才能将所有边的权值变为零。当然还有另外的一个 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”