<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="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.
</div><div class="part" title="Input">
First line is a single integer T(T&lt;=10), indicating the number of test cases. 
<p>For each test case,in the first line there are two numbers n(2&lt;=n&lt;=40000) and m (1&lt;=m&lt;=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&lt;k&lt;=40000).The houses are labeled from 1 to n.</p>
<p>Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.</p>
</div><div class="part" title="Output">
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
</div><div class="output part" title="Sample Output">
10
25
100
100
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p><a href="/post/Algorithm/LCA.html">倍增最近公共祖先</a>模板题</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp How far away? <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <cmath><br>
#include <cstdio><br>
#include <cstring><br>
#include <iostream><br>
#include <vector><br>
using namespace std;</p>
<p>#define Log(format, ...) // printf(format, ##<strong>VA_ARGS</strong>)</p>
<p>const int maxn = 40005;<br>
const int maxlog = 17;</p>
<p>int n, m;</p>
<p>struct Edge {<br>
int c, w;<br>
Edge(int _c = 0, int _w = 0) : c(_c), w(_w) {}<br>
};</p>
<p>vector<Edge> edges[maxn];</p>
<p>void addEdge(int u, int v, int w) {<br>
Log(&quot;addEdge(%d,%d,%d)\n&quot;, u, v, w);</p>
<pre><code>edges[u].push_back(Edge(v, w));
edges[v].push_back(Edge(u, w));
</code></pre>
<p>}</p>
<p>int depth[maxn];<br>
int parent[maxn][maxlog];<br>
int weight[maxn][maxlog];</p>
<p>void lca() {<br>
for (int j = 1; j &lt; maxlog; ++j) {<br>
for (int i = 1; i &lt;= n; ++i) {<br>
parent[i][j] = parent[parent[i][j - 1]][j - 1];<br>
weight[i][j] = weight[i][j - 1] + weight[parent[i][j - 1]][j - 1];<br>
}<br>
}<br>
}</p>
<p>int query(int a, int b) {<br>
Log(&quot;Log(%d,%d)\n&quot;, a, b);</p>
<pre><code>int ans = 0;
if (depth[a] &lt; depth[b])
    swap(a, b);
while (depth[a] != depth[b]) {
    int dis = depth[a] - depth[b];
    int step = (int)(log(dis) / log(2));
    Log(&quot;\t%d-&gt;%d (%d)\n&quot;, a, parent[a][step], weight[a][step]);
    ans += weight[a][step]; // 由于这里还要用到a,因此a要在后面再赋值
    a = parent[a][step];
}
Log(&quot;\tthe same depth %d %d\n&quot;, a, b);
while (a != b) {
    int step = 0;
    for (int i = 0; i &lt; maxlog; ++i) {
        if (parent[a][i] == parent[b][i]) {
            step = i - (i ? 1 : 0);
            break;
        }
    }
    Log(&quot;\tstep: %d a: %d-&gt;%d (%d)  b: %d-&gt;%d (%d)\n&quot;, step, a,
        parent[a][step], weight[a][step], b, parent[b][step],
        weight[b][step]);
    ans += weight[a][step] + weight[b][step];
    a = parent[a][step];
    b = parent[b][step];
}
return ans;
</code></pre>
<p>}</p>
<p>void dfs(int t, int deep) {<br>
depth[t] = deep;<br>
for (auto edge : edges[t]) {<br>
int child = edge.c;<br>
if (parent[t][0] != child) {<br>
parent[child][0] = t;<br>
weight[child][0] = edge.w;<br>
dfs(child, deep + 1);<br>
}<br>
}<br>
}</p>
<p>void init() {<br>
memset(parent, 0, sizeof(parent));<br>
for (int i = 0; i &lt;= n; ++i) {<br>
edges[i].clear();<br>
}<br>
}</p>
<p>int main() {<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>int T;
cin &gt;&gt; T;
while (T--) {
    cin &gt;&gt; n &gt;&gt; m;
    init();

    for (int i = 1; i &lt; n; ++i) {
        int u, v, w;
        cin &gt;&gt; u &gt;&gt; v &gt;&gt; w;
        addEdge(u, v, w);
    }

    dfs(1, 0);
    lca();

    for (int i = 0; i &lt; m; ++i) {
        int a, b;
        cin &gt;&gt; a &gt;&gt; b;
        cout &lt;&lt; query(a, b) &lt;&lt; endl;
    }
}
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

HDU 2586.How far away?