标签归档:LCA

BZOJ 3631: [JLOI2014]松鼠的新家(差分)

Description

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。
可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。维尼是个馋家伙,立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

Input

第一行一个整数n,表示房间个数
第二行n个整数,依次描述a1-an
接下来n-1行,每行两个整数x,y,表示标号x和y的两个房间之间有树枝相连。

Output

一共n行,第i行输出标号为i的房间至少需要放多少个糖果,才能让维尼有糖果吃。

Sample Input

5
1 4 5 3 2
1 2
2 4
2 3
4 5

Sample Output

1
2
1
2
1

HINT

2<= n <=300000

昨天多校有个题类似的思路,但是我主席树写崩了。。。

这个题本质上就是一段路径+1,然后询问每个点的最后的值。然后我们可以在u和v加上1,这样的话我们需要在lca处减1然后lca的父亲也需要减1,这样的话一次树形dp就可以了。但是这样的话我们路径中的点除第一个点外都多计算了一次需要最后减去。。。

 

RCC 16 3rd qualification round D Tree(线段树+LCA)

Nick has got a rooted tree with n vertices as his birthday present.

Recall that a rooted tree is a connected undirected graph, one vertex is chosen as a root. For each vertex the closest to the root neighbor is called the parent of this vertex, other neighbors are its children. The root has no parent. Nick’s tree has vertices numbered from 1 to n, vertex with number 1 is the tree root.

Nick has decided to play with his tree. He chooses some vertex u and removes it, connecting the vertices that were its children to the former parent vertex of u. The root is never removed. But it is not interesting to just remove the vertices, so sometimes he asks for the length of the path from one vertex to another in the current tree. Answer to Nick’s questions.

Input format The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of vertices in the initial tree. The second line contains n - 1 integers pi (1 ≤ pi ≤ n) — parents of vertices 2, 3, …, n.

The third line contains integer q (1 ≤ q ≤ 100 000) — the number of queries. Each of the following q lines contains queries. Each query starts with a query type — an integer equal either to 1 or to 2. If the query type is 1, it is followed by a and b (1 ≤ a, b ≤ n) — the numbers of vertices the distance between which must be found. If the query type is 2, one integer v (1 ≤ v ≤ n) follows — the number of the vertex to remove.

It is guaranteed that the initial tree is given correctly, the vertices in queries are not removed yet, and the root is never removed.

Output format For each query of type 2 print the distance between the corresponding vertices, one per line.
Examples

Input data

Output data

题意:给出一棵\(n\)个点的树,有两种操作:第一种是删去某个点以及他们的所有边,把他的子树们接到他的父亲上。第二种是询问树上两点之间的距离。\(1 \leq n \leq 100000, 1 \leq q \leq 100000\)。

马大爷说LCT可以做,但是蒻根本不会QAQ。。。

考虑删点有什么影响,也就是被删掉的点的子树到根的距离都少了\(1\),那么我们记录下所有点到根的距离,然后每次删点某个点就把它的子树所有点到根的距离减1。那么询问的时候,因为不会询问已经删除的点,那么直接求这两个点的LCA即可,即便这个LCA可能已经删除也无所谓,因为我们不再关心结构,而只是计算距离,只要距离更新了就可以了。

那么通过dfs序,转化成区间减的问题,线段树或者树状数组就行了。。时间复杂度:\(O((q+n)logn)\)。

 

BZOJ 1832: [AHOI2008]聚会&1787: [Ahoi2008]Meet 紧急集合(求树上三点距离和最小)

Description

Y岛风景美丽宜人,气候温和,物产丰富。Y岛上有N个城市,有N-1条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是,小可可通过这些道路可以走遍Y岛的所有城市。神奇的是,乘车经过每条道路所需要的费用都是一样的。小可可,小卡卡和小YY经常想聚会,每次聚会,他们都会选择一个城市,使得3个人到达这个城市的总费用最小。 由于他们计划中还会有很多次聚会,每次都选择一个地点是很烦人的事情,所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置,希望你为他们的每一次聚会选择一个合适的地点。

Input

第一行两个正整数,N和M。分别表示城市个数和聚会次数。后面有N-1行,每行用两个正整数A和B表示编号为A和编号为B的城市之间有一条路。城市的编号是从1到N的。再后面有M行,每行用三个正整数表示一次聚会的情况:小可可所在的城市编号,小卡卡所在的城市编号以及小YY所在的城市编号。

Output

一共有M行,每行两个数Pos和Cost,用一个空格隔开。表示第i次聚会的地点选择在编号为Pos的城市,总共的费用是经过Cost条道路所花费的费用。

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
 

Sample Output

5 2
2 5
4 1
6 0
数据范围:
100%的数据中,N<=500000,M<=500000。
40%的数据中N<=2000,M<=2000。

和Y型项链一样,先思考两个点距离最小肯定是这两个点的LCA,那么枚举一下哪两个点就好了。粘了个原来的LCA板子居然MLE了。。。一看是父亲数组开得太大了QWQ

 

 update:发现和1787是一个题。。。