夏荷浅梦

未归档

读书笔记(1) 题解(6)

/ 注册

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

洛谷P3038 牧草种植Grass Planting

思路：首先，这道题的翻译是有问题的(起码现在是)，查询的时候应该是查询某一条路径的权值，而不是某条边(坑死我了)。与平常树链剖分题目不同的是，这道题目维护的是边权，而不是点权，那怎么办呢？好像有点棘手诶，这是一种非常经典的题型，我们可以发现，一个点最多只有一个父亲！！！那，我们显然就可以用这...

洛谷树链剖分线段树

2018-12-31

0 448

洛谷P3258 [JLOI2014]松鼠的新家

题目描述松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有\(n-1\)根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去\(a_1\)，再去...

洛谷树链剖分线段树

2018-12-31

0 450

洛谷 P3128 [USACO15DEC]最大流Max Flow

题目描述 \(FJ\)给他的牛棚的\(N(2≤N≤50,000)\)个隔间之间安装了\(N-1\)根管道，隔间编号从\(1\)到\(N\)。所有隔间都被管道连通了。 \(FJ\)有\(K(1≤K≤100,000)\)条运输牛奶的路线，第\(i\)条路线从隔间\(s_i\)运输到隔间\(t_i\)...

树链剖分线段树洛谷

2019-01-05

0 593

CF438D The Child and Sequence

题意大意给定数列，区间查询和，区间取模，单点修改。 \(n\),\(m\)小于\(10^5\) 题目描述 At the children's day, the child came to Picks's house, and messed his house up. Picks was a...

CF 树链剖分线段树

2019-01-05

0 516

洛谷P2146 [NOI2015]软件包管理器

题目描述 \(Linux\)用户和\(OSX\)用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。\(Debian/Ubuntu\...

洛谷树链剖分线段树

2019-01-05

0 418

SP375 QTREE - Query on a tree

题意大意给定\(n\)个点的树，边按输入顺序编号为\(1,2,...n-1\)，要求作以下操作： CHANGE \(i\) \(t_i\) 将第\(i\)条边权值改为\(t_i\)，QUERY \(a\) \(b\) 询问从\(a\)点到\(b\)点路径上的最大边权有多组测试数据，每组数据以...

线段树树链剖分 SPOJ

2019-01-05

0 501

洛谷P3398 仓鼠找sugar

题目描述小仓鼠的和他的基\(（mei）\)友\(（zi）sugar\)住在地下洞穴中，每个节点的编号为\(1\)~\(n\)。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室\(（a）\)到餐厅\(（b）\)，而他的基友同时要从他的卧室\(（c）\)到图书馆\(（d）\)。他们都会走最短路径...

LCA 洛谷树链剖分

2019-01-05

0 457