HPU Summer Day23(河南理工大学暑期第二十三天)

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:
这个题的意思就是给你一个图，边的权值也都告诉你了。问你两个点到他们最大公共祖先的距离之和。

这个也是个板子题。但是我们在计算的过程中，要记录一下当前点到达根节点的距离。方便一会计算的时候使用。这是我是用了链式前向星，这样处理距离的话会比较方便。

另外需要注意的就是最后距离的计算是这样计算的，假设两个点事u,v，那么最后的距离是这样计算的

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

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

这个应该还是很好理解的，u到根节点的距离和v到根节点的距离加上之后，他们的最大公共祖先到根节点的距离相当于加了两次，所以减去这个就是两个点到他们最大公共祖先的距离之和了。

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int sijia=1e5;
int f[sijia][30],dis[sijia],dep[sijia],head[sijia];
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];
void add(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    edge[tot].w=w;
    head[u]=tot++;
}
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];
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        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(head,-1,sizeof(head));
        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);
            add(u,v,w);
            add(v,u,w);
        }
        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:
这道题就是给你一个图，问你某两个点的最大公共祖先。

板子题，但是输入算是个小难点吧。可以直接用scanf的格式控制，美滋滋。

好久没用scanf的多组输入，TLE三次，我可真是个弟弟。
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:
这道题跟B题很像，题意我也没搞懂，但是一看样例。就知道跟b一样。。。
就不多说了吧。

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int sijia=1e5;
int f[sijia][30],flag[sijia],dis[sijia],dep[sijia],head[sijia];
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];
void add(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    edge[tot].w=w;
    head[u]=tot++;
}
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];
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        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(head,-1,sizeof(head));
        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);
            add(u,v,w);
            add(v,u,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: