抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

树上差分

树上差分 描述 把差分数组(不是前缀和)放到一个树上,使某个节点的权值等于其本身加上所有子节点的差分的那个值的和。(语无伦次) 差分数组的作用是使区间修改的时间复杂度更低,对应到树上,就可以应用到类似于这样的情况: 点的差分 给A—B的简单路径上所有的节点的权值增加1。 可以把这条路径拆成两条链,分别为A到L(A和B的LCA)和B到L。 把A与B的标记增加1,那么A到L和B到L对应...

洛谷 P3128 最大流Max Flow

P3128 [USACO15DEC]最大流Max Flow 题面 题目描述 FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道,隔间编号从1到N。所有隔间都被管道连通了。 FJ有K(1≤K≤100,000)条运输牛奶的路线,第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力,你需要计算压力最大的隔间...