QTREE 7 - Query on a tree VII
2016-03-18
题目地址 终于刷完了!!
分析 链分治。大综合,前面的都完成了的话,这个应该不难。
代码 // Created by Sengxian on 3/17/16.
// Copyright (c) 2016年 Sengxian. All rights reserved.
// Spoj QTREE VII 链分治(巨坑之后的黎明)
#include &l......
QTREE 5 - Query on a tree V
2016-03-18
题目地址
分析 链分治,不过要注意这个题目由于是求最短路径,而且 没有 边权,所以不用担心走到上面的链之后又走下来,那样如果下面的链有答案的话,只会更长!
代码 // Created by Sengxian on 3/17/16.
// Copyright (c) 2016年 Sengxian. All rights reserved.
// Spoj ......
QTREE 6 - Query on a tree VI
2016-03-18
题目地址
分析 链分治,因为是求和,所以要去重,从什么地方爬上去的,就减什么地方的 m a x L maxL m a x L 。要想清楚,合并的时候什么值该加,什么值不该加。 还有转换颜色的时候,被转换的节点的堆要重新更新,一定不要再次遍历儿子,菊花图会被卡成翔,应该记录两个堆,一个记录同色的,一个记录不同色的,然后 swap......
QTREE 4 - Query on a tree IV
2016-03-18
题目地址
分析 这题是链分治了,某种程度上像最大子段和,也是分治的运用,见 qzc 论文。这题是做后面三题的基础,一定要想清楚! 我是论文
代码 // Created by Sengxian on 3/16/16.
// Copyright (c) 2016年 Sengxian. All rights reserved.
// Spoj QTREE ......
QTREE 3 - Query on a tree again!
2016-03-16
题目地址
分析 还是上树链剖分,线段树里面维护每个节点的颜色,由于每个节点到根节点最多经过 log n \log n lo g n 条轻边,所以我们把到根的路径记下来,然后反着向下找,一旦一个区间的和不为 0,说明有黑点,这时二分(要求点的深度尽量小)去找这个黑点即可,复杂度是 O ( n log 2 n ......
QTREE 2 - Query on a tree II
2016-03-16
题目地址
描述 给你一个 n ( n ≤ 1 0 0 0 0 ) n(n\le 10000) n ( n ≤ 1 0 0 0 0 ) 个节点的树,现在要你支持两种操作:
DIST a b 询问 a a a 到 b b ......
QTREE 1 - Query on a tree I
2016-03-16
题目地址 开始打 QTREE 系列。
描述 给你一个 n ( n ≤ 1 0 0 0 0 ) n(n\le 10000) n ( n ≤ 1 0 0 0 0 ) 个节点的树, 现在要你支持两种操作:
QUERY a b 询问 a a a 到 ......