Article From:https://www.cnblogs.com/Lin88/p/9510766.html

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 23506    Accepted Submission(s): 9329

Problem 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 100
1 2
2 1
 

Sample Output

10
25
100
100
 
 
The main idea of this topic:
  A tree and a tree edge length are given, and a series of query points are given to find the distance between two points.
 
Ways of solving problems:
  In this paper, the shortest distance from the root node to each point can be obtained by Tarjan algorithm, and then the nearest common ancestor (LCA) can be obtained by combining and searching set. The distance between the two points can be expressed as: the distance from the root node to the point 1 + the distance from the root node to the point 2 – twice the distance from the root node to the LCA.The distance.
  The core of thought is to seek LCA, so this paper records a method of combining Tarjan with LCA.
  Realization method: Choose a point as the root node, search the tree by DFS, and connect the child node to the parent node when searching backtracking. When searching for each point, check whether it is a query point, if it is, check whether the corresponding query point has been visited, if it has been visited, thenWhy is it that the father of his father must know their public ancestors? This is what I think about when I look at other great God codes for a while. According to the characteristics of DFS search, when searching for traceback, the subordinate and search information are linked up, while DFS is depth-first, then the traceback distance.The distance must be as small as possible, that is, if you look back one level and find another way, you will continue to search down, and if there is one of the pairs of inquiry points on each of the two roads, the node that was searched for and the information gathered is only one level up, that is, the nearest common ancestor. When dealing with the query point,If you find these and look up the corresponding points that have been modified (that is, visited), just write down the LCA of both of them.
  When the whole tree is traversed, all the LCA of the inquiry point pairs are also calculated. Finally, according to the inquiry order, the distance is calculated and output according to the formula.
 
Combined with AC code understanding:
#include<bits/stdc++.h>
using namespace std;
#define N 40000

typedef struct Edge
{
    int t,v;
    int next;
}edge;

edge E[N*2],e[N*2];
int cnt;
int head1[N],head2[N];//head1For tree node connection, Head2 is used to query the connection of nodes.
int dis[N],f[N],vis[N];//disThe distance from each point to the root node is f.
int ans[N][3];          //ans[0]And [1] records query points, ans[3] records their common ancestor (LCA).
int n,m;
void addedge(int u,int v,int d,edge *a,int *head)
{
    a[cnt].t=v;
    a[cnt].v=d;
    a[cnt].next=head[u];
    head[u]=cnt++;

    a[cnt].t=u;
    a[cnt].v=d;
    a[cnt].next=head[v];
    head[v]=cnt++;
}

int findx(int a)//And check set
{
    if(a!=f[a])
        return f[a]=findx(f[a]);
    return a;
}

void getLCA(int p)//TarjanAlgorithm for LCA
{
    vis[p]=1;
    f[p]=p;        //Initialize and check sets when entering.

    for(int i=head2[p];i!=-1;i=e[i].next)//Check the query point and see if it has been accessed.
    {
        if(vis[e[i].t])
            ans[e[i].v][2]=findx(e[i].t);
    }

    for(int i=head1[p];i!=-1;i=E[i].next)//DFSsearch
    {
        if(!vis[E[i].t])
        {
            dis[E[i].t]=dis[p]+E[i].v;  //Update distance
            getLCA(E[i].t);
            f[E[i].t]=p;                //Union search for updating child nodes after search
        }
    }
}

int main()
{
    //freopen("a.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(head1,-1,sizeof(head1));
        memset(head2,-1,sizeof(head2));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n-1;i++)
        {
            int a,b,v;
            scanf("%d%d%d",&a,&b,&v);
            addedge(a,b,v,E,head1);
        }
        cnt=0;
        for(int i=1;i<=m;i++)       //First record and then process offline.
        {

            scanf("%d%d",&ans[i][0],&ans[i][1]);
            addedge(ans[i][0],ans[i][1],i,e,head2);
        }

        memset(vis,0,sizeof(vis));
        dis[1]=0;
        getLCA(1);

        for(int i=1;i<=m;i++)
            printf("%d\n",dis[ans[i][1]]+dis[ans[i][0]]-2*dis[ans[i][2]]);
    }       //The shortest distance = the distance of node 1 + the distance between node 2 - the shortest distance of 2*LCA.
}           //(The shortest distance is the distance between the root nodes.

 

Leave a Reply

Your email address will not be published. Required fields are marked *