题目链接：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): 28758 Accepted Submission(s): 11562
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 1 2 100 1 2 2 1
Sample Output 10 25 100 100 题意就是给一个树，每个边都是无向的并且由正权值。有T个样例，每个样例有m次询问，找两点之间的路径长度。
我刚开始看到这一题，思路就已经跑偏了，完全没想最近公共祖先，而是想的最短路径。由于数据范围比较大，并且还有查询，所以按照最短路跑一定会T，于是专牛角尖的我遍继续按照最短路的想法，想着如何优化算法，在错误的路上一去不复返。 其实想到最近公共组先的思路以后就很简单了。用倍增思想，先预处理数组f(i,k)和数组dis(i,k)；其中f(i,k)表示节点i的第2的k次方辈祖先是哪个节点，dis(i,k)表示节点i距离它第2的k次方辈祖先的距离是多少。考虑到f(i,k)=f(f(i,k-1),k-1)，dis(i,k)=dis(i,k-1)+dis(f(i,k-1),k-1)，于是对于每一个节点x都可以递推得到所有的f(x,k),dis(x,k)，所以可以用nlogn的时间，用bfs预处理出所有节点的f(i,k)和dis(i,k)的值。然后就是询问了。对于每一次询问想x，y，假设d[x]>d[y]，那么用k=logn…2,1,0进行遍历，如果d[f(x,k)]>=d[y]，就先更新lenx（从x到最近公共祖先的距离，leny同理）的值，lenx+=dis(x,k)，然后更新x，x=f(x,k)，当d[x]==d[y]时结束循环。这时就得到了拥有深度相同的x与y的值。此时对x和y同步向上更新，依然是用k=logn,…2,1,0进行循环，这时如果f(x,k)等于0（即不存在这个点），或者f(x,k)==f(y,k)，都continue掉，如果f(x,k)==f(y,k)，那么就break就行了，不然持续更新lenx，leny，x，y的值就行。最后，如果x！=y，那么就把x=f(x,0),y=f(y,0)（不要忘了更新lenx和leny），此时x，y就一定相等了。答案就是lenx+leny。 （其实dis只需要一维就够了，维护目前节点到根的距离，因为是树状结构，最后如果最近公共祖先是z，那么答案就是d[x]+d[y]-2*d[z]。但是为了强调倍增思想在树中的重要性，就都用倍增思想来维护了。）
