### Nearest Common Ancestors

Description:
A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:

In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

Sample Input

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

Sample Output

4
3

Problem solving:

Code:

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
long long bit[30];
const int xiaozhu = 52121;
void init()
{
bit[0]=1;
for(int i=1;i<=29;i++)    bit[i]=bit[i-1]*2;
}
vector<int> sijia[xiaozhu];
int dep[xiaozhu],p[xiaozhu],f[xiaozhu][30],ai[xiaozhu];
void dfs(int x,int p)
{
dep[x]=dep[p]+1;
f[x][0]=p;
for(int i=1;i<=29;i++)    f[x][i]=f[f[x][i-1]][i-1];
for(int i=0;i<sijia[x].size();i++)
{
if(sijia[x][i]!=p)    dfs(sijia[x][i],x);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])    swap(x,y);
int dif=dep[x]-dep[y];
for(int i=29;i>=0;i--)
{
if(dif>=bit[i])
{
x=f[x][i];
dif-=bit[i];
}
}
if(x==y)    return x;
for(int i=29;i>=0;i--)
{
if(dep[x]>=bit[i]&&f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main()
{
int n,m,u,v;
init();
scanf("%d",&n);
while(n--)
{
memset(f,0,sizeof(f));
memset(dep,0,sizeof(dep));
memset(p,0,sizeof(p));
memset(sijia,0,sizeof(sijia));
memset(ai,0,sizeof(ai));
scanf("%d",&m);

for(int i=1;i<m;i++)
{
scanf("%d %d",&u,&v);
sijia[u].push_back(v);
sijia[v].push_back(u);
ai[v]=1;
}
for(int i=1;i<=m;i++)
{
if(ai[i]==0)
{
dfs(i,0);
break;
}
}
scanf("%d %d",&u,&v);
printf("%d\n",lca(u,v));
//        cout<<"?";
}
}


### Distance Queries

Description:
Farmer John's cows refused to run in his marathon since he chose a path much too long for their leisurely Lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ's distance queries as quickly as possible!
Input

• Lines 1..1+M: Same format as "Navigation Nightmare"
• Line 2+M: A single integer, K. 1 <= K <= 10,000
• Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms.

Output

• Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance.

Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6

Sample Output

13
3
36

Hint

Farms 2 and 6 are 20+3+13=36 apart.

Problem solving:

ans=dis[u]+dis[v]-2*dis[lca(u,v)]


dis数组代表的是当前点到根节点的距离

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int sijia=1e5;
int n,m,tot=0;
long long bit[30];
void init()
{
bit[0]=1;
for(int i=1;i<=29;i++)
bit[i]=2*bit[i-1];
}
struct node{
int to,next,w;
}edge[sijia];
{
edge[tot].to=v;
edge[tot].w=w;
}
void dfs(int x,int y)
{
f[x][0]=y;
for(int i=1;i<=29;i++)
f[x][i]=f[f[x][i-1]][i-1];
{
if(edge[i].to!=y)
{
dis[edge[i].to] = dis[x]+edge[i].w;//这个就是处理距离的过程，最后dis数组就是第i个点到根节点的距离
dep[edge[i].to] = dep[x] + 1;
dfs(edge[i].to,x);
}
}
}
int lca(int x,int y)
{
int xx=x,yy=y;
if(dep[x]<dep[y])   swap(x,y);
int dif=dep[x]-dep[y];
for(int i=29;i>=0;i--)
{
if(dif>=bit[i])
{
x=f[x][i];
dif-=bit[i];
}
}
if(x==y)    return dis[xx]+dis[yy]-2*dis[x];
for(int i=29;i>=0;i--)
{
if(dep[x]>=bit[i]&&f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return dis[xx]+dis[yy]-2*dis[f[x][0]];//这就是那个计算公式
}

int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
tot=0;
memset(f,0,sizeof(f));
memset(dis,0,sizeof(dis));
memset(dep,0,sizeof(dep));
init();
int u,v,w;
char s;
for(int i=0;i<m;i++)
{
scanf("%d %d %d %c",&u,&v,&w,&s);
}
dep[0]=0;
dfs(1,0);
int k;
scanf("%d",&k);
for(int i=0;i<k;i++)
{
scanf("%d %d",&u,&v);
printf("%d\n",lca(u,v));
}
}
}


### Closest Common Ancestors

Description:
Write a program that takes as input a rooted tree and a list of pairs of vertices. For each pair (u,v) the program determines the closest common ancestor of u and v in the tree. The closest common ancestor of two nodes u and v is the node w that is an ancestor of both u and v and has the greatest depth in the tree. A node can be its own ancestor (for example in Figure 1 the ancestors of node 2 are 2 and 5)

The data set starts with the tree description, in the form:

nr_of_vertices
vertex:(nr_of_successors) successor1 successor2 ... successorn
......

where vertices are represented as integers from 1 to n. The tree description is followed by a list of pairs of vertices, in the form:

nr_of_pairs
(u v) (x y) ...

The input contents several data sets (at least one).

Note that white-spaces (tabs, spaces and line breaks) can be used freely in the input.

For each common ancestor the program prints the ancestor and the number of pair for which it is an ancestor. The results are printed on the standard output on separate lines, in to the ascending order of the vertices, in the format: ancestor:times

For example, for the following tree:

the program input and output is:

Input

5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5) (1,4) (4,2)
(2,3)
(1,3) (4,3)

Output

2:1
5:5

Problem solving:

Code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
long long bit[30];
const int xiaozhu = 52121;
void init()
{
bit[0]=1;
for(int i=1;i<=29;i++)    bit[i]=bit[i-1]*2;
}
vector<int> sijia[xiaozhu];
int flag[xiaozhu],ans[xiaozhu],dep[xiaozhu],p[xiaozhu],f[xiaozhu][30];
void dfs(int x,int p)
{
dep[x]=dep[p]+1;
f[x][0]=p;
for(int i=1;i<=29;i++)    f[x][i]=f[f[x][i-1]][i-1];
for(int i=0;i<sijia[x].size();i++)
{
if(sijia[x][i]!=p)    dfs(sijia[x][i],x);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])    swap(x,y);
int dif=dep[x]-dep[y];
for(int i=29;i>=0;i--)
{
if(dif>=bit[i])
{
x=f[x][i];
dif-=bit[i];
}
}
if(x==y)    return x;
for(int i=29;i>=0;i--)
{
if(dep[x]>=bit[i]&&f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main()
{
int n,a,b,c;
init();
while(scanf("%d",&n)!=EOF)
{
memset(flag,0,sizeof(flag));
memset(ans,0,sizeof(ans));
memset(p,0,sizeof(p));
memset(f,0,sizeof(f));
memset(sijia,0,sizeof(sijia));
for(int i=0;i<n;i++)
{
scanf("%d:(%d)",&a,&b);
while(b--)
{
scanf("%d",&c);
sijia[a].push_back(c);
sijia[c].push_back(a);
flag[c]=1;
}
}
for(int i=1;i<=n;i++)
{
if(!flag[i])
{
dep[i]=0;
dfs(i,0);
break;
}
}
int m,u,v;
char s;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf(" (%d,%d)",&u,&v);
ans[lca(u,v)]++;
}
for(int i=1;i<=n;i++)
{
if(ans[i])  printf("%d:%d\n",i,ans[i]);
}
}
}


### How far away ？

Description:
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input

First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1

Sample Output

10
25
100
100

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int sijia=1e5;
int n,m,tot=0;
long long bit[30];
void init()
{
bit[0]=1;
for(int i=1;i<=29;i++)
bit[i]=2*bit[i-1];
}
struct node{
int to,next,w;
}edge[sijia];
{
edge[tot].to=v;
edge[tot].w=w;
}
void dfs(int x,int y)
{
f[x][0]=y;
for(int i=1;i<=29;i++)
f[x][i]=f[f[x][i-1]][i-1];
{
if(edge[i].to!=y)
{
dis[edge[i].to] = dis[x]+edge[i].w;
dep[edge[i].to] = dep[x] + 1;
dfs(edge[i].to,x);
}
}
}
int lca(int x,int y)
{
int xx=x,yy=y;
if(dep[x]<dep[y])   swap(x,y);
int dif=dep[x]-dep[y];
for(int i=29;i>=0;i--)
{
if(dif>=bit[i])
{
x=f[x][i];
dif-=bit[i];
}
}
if(x==y)    return dis[xx]>dis[yy]?(dis[xx]-dis[yy]):(dis[yy]-dis[xx]);
for(int i=29;i>=0;i--)
{
if(dep[x]>=bit[i]&&f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return dis[xx]+dis[yy]-2*dis[f[x][0]];
}

int main()
{
scanf("%d",&n);
while(n--)
{
tot=0;
memset(f,0,sizeof(f));
memset(dis,0,sizeof(dis));
memset(dep,0,sizeof(dep));
init();
int u,v,w,mm,p;
scanf("%d %d",&mm,&p);
for(int i=1;i<mm;i++)
{
scanf("%d %d %d",&u,&v,&w);
}

dep[0]=0;
dfs(1,0);
for(int i=0;i<p;i++)
{
scanf("%d %d",&u,&v);
printf("%d\n",lca(u,v));
}
}
}


### Equivalent Sets

Description:
To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.
Input

The input file contains multiple test cases, in each case, the first line contains two integers N <= 20000 and M <= 50000.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.

Output

For each case, output a single integer: the minimum steps needed.

Sample Input

4 0
3 2
1 2
1 3

Sample Output

4
2

Problem solving:

Code: