喜欢的话就坚持吧

分类目录
10月 18

题目大意

给你一张n个点m条边的图,让你求出从1号节点出发到所有点的最短路,问不能选每条最短路到终点的前一条边时,1号点到所有点的最短路分别是多少?无解输出-1,保证原来的最短路唯一。
n<=100,000 m<=200,000;

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 19

点分治一般都是处理树上路径用的。
比如问你树上距离为x的点对有多少个?
之类的。

按照传统惯例,本文从是什么,为什么,做么做三个方面讲解。

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 18

题目大意

给你一棵树,他会给你指定一个到达每个点的顺序,问每个点被经过了几次。最后到的那个点不算次数。

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 16

题目大意

给你一张n个点的无向图,求两对点间最短路的最长公共路径。
无重边,无自环
n<=1500

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 14

题目大意

给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

8月 31

题目大意:

给你一棵树,每个点有点权,让你支持③种操作

(1)点x值加y

(2)以点x为根的子树加y

(3)定义(u,v)为u和v的点权和。求∑(u,v) (u<v&&lca(u,c)=x)

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。