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的。具体细节请看代码。

 

hdu 6200 mustedge mustedge mustedge(并查集+树状数组)》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注