Phecda_

未归档

/ 注册

全部文章 / 未归档（共3篇）

LuoGu P2783 有机化学之神偶尔会做作弊

题目传送门人生第一道黑题呢,虽然这题是黑题中的水题并且我调了一整节课,但是我还是很兴奋啊.毕竟人生第一道黑题啊这个题根据题意，先把整个图进行tarjan缩点，建出一棵树，对于每一组询问，两点之间的距离+1就是答案，求出他们的LCA，两点到LCA的距离之和就是两点之间的距离然后....LCA我采...

tarjan缩点 SCC 树链剖分

2018-09-11

0 466

USACO15DEC最大流MaxFlow

传送门这是个假的最大流,其实是一个用树剖+线段树就能解决的事情题目中的道路会对路径上的造成压力,最后询问最大的压力其实就等价于对每条路径上的点加上 1 的权值,并且最后询问整个树中的最大值然后树剖+最大值线段树裸题,完事,莫得别的问题了. \(Updated:\) 其实,可以树上差...

树链剖分线段树差分

2019-04-28

0 486

ZROI#987

ZROI#987 差分+简单数学即可. 首先有个性质: 两条链相交等价于其中一条链的\(LCA\)在另一条链上. 于是我们就对每一条链的\(LCA\)都加\(1\). 最后查询每一条链的区间和即可.树剖实现. 但这样我们会算重复,就是说\((a,b)\)两条链相交我们会算\((a,b)\)一次,\...

nature 差分树链剖分线段树容斥原理

2019-09-15

0 495