模板倍增LCA 求树上两点距离 hdu2586

#define _CRT_SECURE_NO_WARNINGS
#include<cmath>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<string.h>
using namespace std;
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a))
#define eps 1e-6
#define pb push_backtypedef long long ll;stack <int> dl;
const int maxn=1e5+;
int f[maxn][];
int fa[maxn];
ll dis[maxn];
int dep[maxn];int n, m;
vector<pair<int,ll> > E[maxn];
void dfs(int rt,int p) { for (int i = ; i < E[rt].size(); i++) {
pair<int,int> v = E[rt][i];
if (v.first == p)continue;
fa[v.first] =rt ;
dep[v.first] =dep[rt]+ ;
dis[v.first] = dis[rt] + v.second;
dfs(v.first, rt);
}
}void Init_LCA() {
for (int j = ; ( << j) <= n; ++j)
for (int i = ; i <= n; ++i)
f[i][j] = -;
for (int i = ; i <= n; ++i) f[i][] = fa[i];
for (int j = ; ( << j) <= n; ++j)
for (int i = ; i <= n; ++i)
if (f[i][j - ] != -)
f[i][j] = f[f[i][j - ]][j - ];
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int i, lg;
for (lg = ; ( << lg) <= dep[x]; ++lg);
--lg;
/// 使x往上走直到和y在同一水平线上；
for (i = lg; i >= ; --i)
if (dep[x] - ( << i) >= dep[y])
x = f[x][i];
if (x == y) return x;
/// 此时x，y在同一水平线上，使x，y同时以相同的速度(2^j)往上走；
for (i = lg; i >= ; --i)
if (f[x][i] != - && f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return fa[x];
}
int main()
{
int t;
cin >> t;
while (t--) { cin >> n >> m;
rep(i, , n)E[i].clear();
//mmm(dis, 0); mmm(fa, 0); mmm(f, 0); mmm(dep, 0);
rep(i, , n-) {
int x, y;
ll z;
scanf("%d%d%lld", &x, &y, &z);
//f[x][0] = y;
E[x].push_back(make_pair(y,z));
E[y].push_back(make_pair(x,z));
}
dis[] = ;
//fa[1] = 1;
//dep[1] = 0;
dfs(, -);
Init_LCA();
rep(i, , m) {
int x, y;
scanf("%d%d", &x, &y);
printf("%lld\n", dis[x] + dis[y] - 2ll * dis[LCA(x, y)]); }
//cout << endl;
}
cin >> n;
return ;
}/*
2
5 2
1 2 10
2 3 10
3 4 10
4 5 10
1 5
5 3 */