标签归档:LCA

BZOJ 2588: Spoj 10628. Count on a tree(主席树)

Description

给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。

Input

第一行两个整数N,M。
第二行有N个整数,其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y),表示点x到点y有一条边。
最后M行每行两个整数(u,v,k),表示一组询问。

Output

M行,表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

HINT

HINT:
N,M<=100000
每个点维护他到根的的路径上的权值线段树,查询的时候我们发现某一段权值区间的个数其实是sum[u]+sum[v]-sum[lca]-sum[lca_father]。所以带着这四个参数一起递归query即可。离散化后lower_bound边界写错了,查了好久。。。

 

BZOJ 1103: [POI2007]大都市meg

Description

  在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了。
不过,她经常回忆起以前在乡间漫步的情景。昔日,乡下有依次编号为1..n的n个小村庄,某些村庄之间有一些双
向的土路。从每个村庄都恰好有一条路径到达村庄1(即比特堡)。并且,对于每个村庄,它到比特堡的路径恰好
只经过编号比它的编号小的村庄。另外,对于所有道路而言,它们都不在除村庄以外的其他地点相遇。在这个未开
化的地方,从来没有过高架桥和地下铁道。随着时间的推移,越来越多的土路被改造成了公路。至今,Blue Mary
还清晰地记得最后一条土路被改造为公路的情景。现在,这里已经没有土路了——所有的路都成为了公路,而昔日
的村庄已经变成了一个大都市。 Blue Mary想起了在改造期间她送信的经历。她从比特堡出发,需要去某个村庄,
并且在两次送信经历的间隔期间,有某些土路被改造成了公路.现在Blue Mary需要你的帮助:计算出每次送信她需
要走过的土路数目。(对于公路,她可以骑摩托车;而对于土路,她就只好推车了。)

Input

  第一行是一个数n(1 < = n < = 2 50000).以下n-1行,每行两个整数a,b(1 < =  a以下一行包含一个整数m
(1 < = m < = 2 50000),表示Blue Mary曾经在改造期间送过m次信。以下n+m-1行,每行有两种格式的若干信息
,表示按时间先后发生过的n+m-1次事件:若这行为 A a b(a若这行为 W a, 则表示Blue Mary曾经从比特堡送信到
村庄a。

Output

  有m行,每行包含一个整数,表示对应的某次送信时经过的土路数目。

Sample Input

5
1 2
1 3
1 4
4 5
4
W 5
A 1 4
W 5
A 4 5
W 5
W 2
A 1 2
A 1 3

Sample Output

2
1
0
1

HINT

 

dfs序后维护树状数组的煞笔题。

 

hdu 6200 mustedge mustedge mustedge(并查集+树状数组)

Problem Description
Give an connected undirected graph with n nodes and m edges, (n,m105) which has no selfloops or multiple edges initially.
Now we have q operations (q105):1 u v: add an undirected edge from u to v(uv&&1u,vn)
2 u v: count the number of mustedges from u to v(1u,vn).

mustedge: we define set Ei as a path from u to v which contain edges in this path, and |k1Ei| is the number of mustedges|x| means size of set x, and E1,E2Ek means all the paths.
It’s guaranteed that n,m,q106
Please note that maybe there are more than one edges between two nodes after we add edges. They are not the same, which means they can be in a set at the same time. Read the sample data for more information.

 

Input
Input starts with an integer T, denoting the number of test cases.
For each case:
First line are two number n and m;
Then next m lines, each contains two integers u and v, which indicates an undirected edge from u to v;
Next line contains a number q, the number of operations;
Then next q lines, contains three integers xu and v where x is the operation type, which describes an operation.

 

Output
For each test case, output “Case #x:” where x is the test case number starting from 1.
In each test case, print a single number one line when query the number of mustedges.

 

Sample Input
2
4 3
1 2
2 3
3 4
5
2 1 4
1 2 3
2 1 4
2 2 3
2 2 4
8 9
1 2
2 3
1 3
3 4
4 5
4 6
5 7
5 8
7 8
5
2 7 8
2 1 6
2 4 7
1 6 8
2 5 6
Sample Output
Case #1: 3 2 0 1
Case #2: 0 2 1 0
这个题比赛的时候居然读错题了,然后一脸懵逼的看着样例,赛后才发现题目求的是两点路径中必须要经过的路径数。。。
可以树剖两个log过,dqs大爷和xy大爷都试过了。我写了个1个log的做法,目前(2017.9.12)是hdu最快的嘿嘿嘿。。。
我们把一开始的图边双连通分量缩点成树,那么此时若发生询问那么一定是两点距离。我们可以维护每个点到根的距离,开个树状数组,差分一下就好了嘛。然后现在发生加边操作,考虑影响就是u和v以及他们的lca之间变成了一个环,我们需要把她们缩点,相当于区间清0,这一步我们可以通过一个并查集来加速,并查集的代表元表示这个并查集里最高的点。可以从LCA断开,分别从u和v向上用并查集合并。每删掉一个点,那么它的子树权值都-1。因为这样的合并修改并查集父亲,最多只会发生n次,每次合并的时候我们会用树状数组来修改,所以加边的复杂度为nlogn,询问直接求个lca就好,也是qlogn的。具体细节请看代码。