Codeforces 809E - Surprise me!

2017-05-28
题目地址 描述 给定一棵 n ( n ≤ 2 0 0 0 0 0 ) n(n\le 200000) n ( n ≤ 2 0 0 0 0 0 ) 个点的树，每个点的点权 a i a_i a ​ i ​ ​ 形成了一个......
Read More

虚树学习笔记

2016-12-20
概述 在 OI 比赛中，有这样一类题目：给定一棵树，另有多次询问，每个询问给定一些关键点，需要求这些关键点之间的某些信息。询问数可能很多，但满足所有询问中关键点数量的总和与树的大小同阶。 由于询问数可以非常多，每次无法遍历整棵树，这类题目看似没有办法做，但实际上，我们可以用一种叫做 虚树（virtual tree） 的技术来解决这一问题。 介绍 简单来说，虚树是对一颗有根树中......
Read More