题目：hdu 6110 路径交
分析：建好树之后dfs获得每个节点的深度，然后建立一颗线段树，每个节点维护一个路径，表示其左子节点维护的路径和右子节点维护的路径相交的路径（一棵树上两个节点相交只有一条路径），这里需要用到lca：即两个路径：a -> b, c -> d相交的路径为这四个节点(lca(a, c), lca(a, d), lca(b, c), lca(b, d))中深度较大的两个节点所连成的路径；
求两点a, b的距离可用公式：dis(a) + dis(b) - 2*dis(lca(a, b))， 其中，dis(a)代表a到达根节点的距离。这样可做到每次查询的时间为log(n)
代码如下：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;typedef pair<int, int> P;
typedef long long ll;const int INF = (int)1e9;
const int maxn = 500000 + 10;int cnt, lst[maxn], nxt[maxn], to[maxn], c[maxn];
int fa[2*maxn][20], dep[2*maxn];
ll dis[2*maxn];P p[2*maxn];
int n, m;
int q1, q2;void add(int u, int v, int d){nxt[++cnt] = lst[u]; lst[u] = cnt; to[cnt] = v, c[cnt] = d;nxt[++cnt] = lst[v]; lst[v] = cnt; to[cnt] = u, c[cnt] = d;
}void dfs(int u, int f){for (int j = lst[u]; j; j = nxt[j]){int v = to[j];if (v == f) continue;dis[v] = dis[u] + c[j];dep[v] = dep[u] + 1;fa[v][0] = u;dfs(v, u);}}void init_lca(){for (int j = 1; (1 << j) <= n; j ++)for (int i = 1; i <= n; i ++)fa[i][j] = fa[fa[i][j-1]][j-1];
}int lca(int a, int b) {if (dep[a] < dep[b]) swap(a, b);int f = dep[a] - dep[b];for (int j = 0; (1 << j) <= f; j ++)if ((1 << j) & f) a = fa[a][j];if (a != b) {for (int j = log2(n) + 1; j >= 0; j --) {if (fa[a][j] != fa[b][j]){a = fa[a][j], b = fa[b][j];}}a = fa[a][0];}return a;}bool cmp(int a, int b) {return dep[a] > dep[b];
}P unit(P t1, P t2){int a[10];a[0] = lca(t1.first, t2.first);a[1] = lca(t1.first, t2.second);a[2] = lca(t1.second, t2.first);a[3] = lca(t1.second, t2.second);sort(a, a + 4, cmp);return P(a[0], a[1]);}void build(int o, int L, int R) {if (L == R) {scanf("%d %d", &p[o].first, &p[o].second);return;}int M = L + (R-L) / 2;build(2*o, L, M);build(2*o + 1, M + 1, R);p[o] = unit(p[2*o], p[2*o + 1]);
}P query(int o, int L, int R) {if (q1 <= L && q2 >= R) {return p[o];}int M = L + (R-L) / 2, lc = 2*o, rc = 2*o + 1;if (q2 <= M) return query(lc, L, M);else if (q1 > M) return query(rc, M + 1, R);else return unit(query(lc, L, M), query(rc, M+1, R));
}int main(){freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);scanf("%d", &n);for (int i = 1; i < n; i ++) {int u, v, d;scanf("%d %d %d", &u, &v, &d);add(u, v, d);}dfs(1, 1);init_lca();scanf("%d", &m);build(1, 1, m);int kase; scanf("%d", &kase);while (kase --) {scanf("%d %d", &q1, &q2);P a = query(1, 1, m);ll ans = dis[a.first] + dis[a.second]-2*dis[lca(a.first, a.second)];printf("%lld\n", ans);}return 0;
}