How far away
&题解：
和上篇是一样的题,这用的是lca方法做的, 不知道为什么,把数组开到80000 就a了 >_<
哈 我现在知道为什么了,因为我的rmq数组没有乘2,rmq比较的是depth数组,但是depth数组的范围是maxn*2,所以rmq的数组乘2就好了
&代码：
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define fd(i,a,b) for(int i=(a);i>=(b);i--)
const int max_v = 40000 + 7;
int rq[max_v*2][20], mm[max_v*2], n, m;
void initRMQ(int n, int b[]) {
mm[0] = -1;
for(int i = 1; i <= n; i++) {
mm[i] = (i & (i - 1)) ? mm[i - 1] : mm[i - 1] + 1;
rq[i][0] = i;
}
for(int j = 1; j <= mm[n]; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
int x = rq[i][j - 1], y = rq[i + (1 << (j - 1))][j - 1];
rq[i][j] = b[x] < b[y] ? x : y;
}
}
int RMQ(int x, int y, int b[]) {
if(x > y) swap(x, y);
int k = mm[y - x + 1];
int x2 = rq[x][k], y2 = rq[y - (1 << k) + 1][k];
return b[x2] < b[y2] ? x2 : y2;
}
int dis[max_v];
struct Edge {
int u, v, w, nx;
} G[2 * max_v];
int root;
int vs[max_v * 2];
int depth[max_v * 2];
int id[max_v];
int cnt, ft[max_v * 2], vis[max_v];
void Add(int u, int v, int w) {
G[cnt].u = u; G[cnt].v = v; G[cnt].w = w;
G[cnt].nx = ft[u];
ft[u] = cnt++;
}
void dfs(int v, int p, int d, int &k) {
id[v] = k;
vs[k] = v;
depth[k++] = d;
// vis[v] = 1;
for(int i = ft[v]; ~i; i = G[i].nx) {
// printf("%d %d-- %d
", G[i].u, G[i].v, p);
if(G[i].v != p) {
dis[G[i].v] = dis[G[i].u] + G[i].w;
dfs(G[i].v, G[i].u, d + 1, k);
vs[k] = v;
depth[k++] = d;
}
}
}
void initLCA() {
int k = 1;
memset(vis, 0, sizeof(vis));
dfs(root, -1, 0, k);
initRMQ(k - 1, depth);
}
int LCA(int u, int v) {
return vs[RMQ(min(id[u], id[v]), max(id[u], id[v]) + 1, depth)];
}
int main() {
//("E:1.in", "r", stdin);
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
cnt = 0;
memset(ft, -1, sizeof(ft));
fo(i, 1, n - 1) {
int x, y, val;
scanf("%d%d%d", &x, &y, &val);
Add(x, y, val);
Add(y, x, val);
}
root = 1;
dis[root] = 0;
initLCA();
fo(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d
", dis[u] + dis[v] - 2 * dis[LCA(u, v)]);
}
}
return 0;
}
这个是用临街矩阵写的,RT了,但有注释
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define fd(i,a,b) for(int i=(a);i>=(b);i--)
#define pii pair<int,int>
//RMQ 相关
const int maxn = 40000 + 7, max_v = maxn;
int dp[maxn][20], mm[maxn], n, m;
void initRMQ(int n, int b[]) {
mm[0] = -1;
for(int i = 1; i <= n; i++) {
mm[i] = (i & (i - 1)) ? mm[i - 1] : mm[i - 1] + 1;
dp[i][0] = i;
}
for(int j = 1; j <= mm[n]; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
int x = dp[i][j - 1], y = dp[i + (1 << (j - 1))][j - 1];
dp[i][j] = b[x] < b[y] ? x : y;
// dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
int RMQ(int x, int y, int b[]) {
if(x > y) swap(x, y);
int k = mm[y - x + 1];
int x2 = dp[x][k], y2 = dp[y - (1 << k) + 1][k];
return b[x2] < b[y2] ? x2 : y2;
}
int dis[maxn];
//LCA 相关
vector<pii> G[max_v]; //图的邻接表
int root;
int vs[max_v * 2]; //dfs访问的顺序
int depth[max_v * 2]; //节点深度
int id[max_v]; //各顶点在vs中首次出现的下标
//v:现节点 p:父节点 d:深度 k:编号
void dfs(int v, int p, int d, int &k) {
id[v] = k;
vs[k] = v;
depth[k++] = d;
for(int i = 0; i < G[v].size(); i++) {
if(G[v][i].first != p) {
dis[G[v][i].first] = dis[v] + G[v][i].second;
dfs(G[v][i].first, v, d + 1, k);
vs[k] = v;
depth[k++] = d;
}
}
}
void initLCA(int V) {
int k = 1;
dfs(root, -1, 0, k);
initRMQ(k - 1, depth);
}
int LCA(int u, int v) {
return vs[RMQ(min(id[u], id[v]), max(id[u], id[v]) + 1, depth)];
}
int main() {
//("E:1.in", "r", stdin);
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
fo(i, 1, n) G[i].clear();
fo(i, 1, n - 1) {
int x, y, val;
scanf("%d%d%d", &x, &y, &val);
G[x].push_back(make_pair(y, val));
G[y].push_back(make_pair(x, val));
}
root = 1;
dis[root] = 0;
initLCA(n);
fo(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d
", dis[u] + dis[v] - 2 * dis[LCA(u, v)]);
}
// for(int i = 0; i < 8; i++) {
// printf("%3d", i);
// } printf("
");
// for(int i = 0; i < 8; i++) {
// printf("%3d", dis[i]);
// } printf("
");
}
return 0;
}