# BZOJ 2588: Spoj 10628. Count on a tree（主席树）

## 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

2
8
9
105
7

HINT：
N,M<=100000

# BZOJ 1103: [POI2007]大都市meg

## Description

在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员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曾经从比特堡送信到

## Output

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

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

2
1
0
1

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