首页 > Max Flow
开通博客写题解
头像 sunrise__sunrise
发表于 2021-04-13 19:41:09
中文题意 给你个节点的一棵树，并且存在次操作，每次操作把节点之间路径上全部的点权值加一。问操作次操作后整棵树最大的权值是多少？ Solution 读懂题的话，就是树上差分模板题，我实现的办法是树链剖分，会了之后就觉得比倍增快乐多了。给个OIWiki的差分链接 树上点差分就是： #include & 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Kur1su
发表于 2021-04-14 10:30:35
Description FJ给他的牛棚的(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。 FJ有(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间运输到隔间。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-04-13 20:53:59
题号 NC24019名称 Max Flow来源 USACO英文版-2015 December Contest-Platinum 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld题目描述 给你一棵树个节点的树 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2021-04-13 23:25:51
咦，竟然之前做过 题解：是一道很经典的树差分模板题， 点差分我们需要让cnt[s]++,让cnt[t]++，而让他们的cnt[lca]--，cnt[faher(lca)]--;边差分cnt[s]++ ， cnt[t]++ ，cnt[LCA]-=2 边差分：边差分的话要把边的权值存在他连着的儿子节点上 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-04-19 23:18:38
题意：有一颗n个节点的树，有k次操作，每次操作给出二个节点，然后将二个节点及二个节点之间的节点权值都加一，然后求最后树中权值最大的节点的权值为多少？ 思路：lca+差分：用lca求出二个节点u、v的最近公共祖先k，k的父亲节点为kp；要使u、v路经上节点权值加一则val[u]、val[v]进行加一， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”