HDU—— 2586 How far away ？（LCA tarjan）

谁借莪１个温暖的怀抱￠ 2021-09-26 11:54 316阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2586][http_acm.hdu.edu.cn_showproblem.php_pid_2586]

题目：

# How far away ？ #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 19788    Accepted Submission(s): 7741**

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

23 21 2 103 1 151 22 32 21 2 1001 22 1

Sample Output

1025100100

题目描述：

LCA（最近公共祖先），这里我用的是tarjan离线算法，头一次写这种题，刚开始还用dijkstar写，，，，后来百度看了这篇博客弄懂的tarjan算法（[https://www.cnblogs.com/JVxie/p/4854719.html][https_www.cnblogs.com_JVxie_p_4854719.html]）。另外两种LCA的方法暂时不会，，，

代码：

#include<stdio.h>
    #include<string.h>
    const int N = 40010;
    const int M = 210;
    int a,b,k;
    struct s
    {
    	int a,b,c,d;
    }sq[M];
    int f[N],q[N],V[N];
    int hs[N];
    struct sf
    {
    	int a,b,c;
    }ss[2*N]; 
    int sh[N],shs[M];
    void qwer(int x,int y,int z)
    {
    	ss[k].a = y;
    	ss[k].b = z;
    	ss[k].c  = hs[x];
    	hs[x] = k ++;
    }
    void tar(int);
    void me(int,int);
    int fg(int);
    int main()
    {
    	int i,j,t;
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d%d",&a,&b);
    		memset(hs,-1,sizeof(hs));
    		k = 1;
    		for(i = 1 ;i < a;i ++){
    			int u,v,w;
    			scanf("%d%d%d",&u,&v,&w);
    			qwer(u,v,w);
    			qwer(v,u,w);
    		}
    		memset(sh,-1,sizeof(sh));
    		for(i = 0;i < b;i ++){
    			scanf("%d%d",&sq[i].a,&sq[i].b);
    			sq[i].c = i;
    			shs[i] = sh[sq[i].a];
    			sh[sq[i].a] = i;
    		}	
    		for(i = 1;i <= a;i ++)
    			f[i] = i;
    		memset(V,0,sizeof(V));
    		memset(q,0,sizeof(q));
    		tar(1);
    		for(i =0 ;i < b;i++)
    			printf("%d\n",sq[i].d);
    	}
    	return 0;
    }
    void tar(int x)
    {
    	int i;
    	V[x] = 1;
    	for(i = hs[x];i != -1;i = ss[i].c){
    		if(!V[ss[i].a ]){
    			q[ss[i].a] = q[x] + ss[i].b ;
    			tar(ss[i].a);
    			me(x,ss[i].a);
    		}
    	}
    	for(i = sh[x];i != -1;i = shs[i]){
    		if(V[sq[i].b]){
    			sq[sq[i].c ].d = q[sq[i].a] + q[sq[i].b ] - 2 * q[fg(sq[i].b)];
    		}
    	}
    }
    void me(int x,int y)
    {
    	x = fg(x);
    	y = fg(y);
    	f[y] = x;
    }
    int fg(int x)
    {
    	if(x == f[x])
    		return f[x];
    	return f[x] = fg(f[x]);
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_2586]: http://acm.hdu.edu.cn/showproblem.php?pid=2586
[https_www.cnblogs.com_JVxie_p_4854719.html]: https://www.cnblogs.com/JVxie/p/4854719.html