HDU 2586 How far away(LCA)
Description
n个点，n - 1条边连起来(构成了一棵树)，无更新操作，查询任意两点间距离
Analyze
Code（RMQ~ST离线做法）
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 41000;
int n, m;
int tot;//遍历数
int dis[N];//距离根节点1的距离
struct node
{
int v, w, pre;
} a[N * 2];
int head[N * 2], cnt = 1;
void add_edge(int u, int v, int w)
{
a[cnt].v = v;
a[cnt].w = w;
a[cnt].pre = head[u];
head[u] = cnt++;
}
bool vis[N];
int first[N];//该点首次出现所对应的的遍历数tot
int point[N * 4];//遍历数tot所对应的那个点的标号
int depth[N * 4];//遍历数tot所对应的那个点的深度
void DFS(int u, int dep)
{
vis[u] = 1;
point[++tot] = u, first[u] = tot, depth[tot] = dep;
for(int i = head[u]; ~i; i = a[i].pre)
{
int v = a[i].v, w = a[i].w;
if(!vis[v])
{
dis[v] = dis[u] + w;
DFS(v, dep + 1);
//退回到这一点也是一次访问
point[++tot] = u, depth[tot] = dep;
}
}
}
int sma[N][20];//存的是某个区间里最小的遍历数tot
void ST()
{
for(int i = 1; i <= n; ++i)
sma[i][0] = depth[i];
for(int j = 1; (1 << j) <= n; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
sma[i][j] = min(sma[i][j - 1], sma[i + (1 << (j - 1))][j - 1]);
}
int RMQ(int l, int r)
{
int k = 0;
while( (1 << (k + 1)) <= r - l + 1 )
++k;
return min(sma[l][k], sma[r - (1 << k) + 1][k]);
}
int LCA(int u, int v)
{
int x = first[u];
int y = first[v];
if(x > y)
swap(x, y);
int res = RMQ(x, y);
return point[res];
}
int main()
{
int _;
scanf("%d", &_);
while(_--)
{
cnt = 1;
scanf("%d%d", &n, &m);
int u, v, w;
memset(head, -1, sizeof(head));
for(int i = 0; i < n - 1; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
tot = 0, dis[1] = 0;
memset(vis, 0, sizeof(vis));
DFS(1, 1);
ST();
while(m--)
{
int u, v;
scanf("%d%d", &u, &v);
int lca = LCA(u, v);
cout << dis[u] + dis[v] - 2 * dis[lca] << '\n';
}
}
return 0;
}
Trajan+并查集(在线做法)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 41000;
const int M = 810;
int n, m;
bool vis[N];
int ance[N];//准lca
int pre[N], dis[N];
struct edge
{
int v, w, pre;
} a[N * 2];
int head[N * 2], cnt;
void add_adge(int u, int v, int w)
{
a[cnt].v = v;
a[cnt].w = w;
a[cnt].pre = head[u];
head[u] = cnt++;
}
struct query
{
int u, v, lca, pre;
} q[N];
int qhead[N * 2], qcnt;
void add_query(int u, int v)
{
q[qcnt].u = u;
q[qcnt].v = v;
q[qcnt].lca = -1;
q[qcnt].pre = qhead[u];
qhead[u] = qcnt++;
}
int found(int x)
{
if(x != pre[x])
pre[x] = found(pre[x]);
return pre[x];
}
void unite(int a, int b)
{
int x = found(a);
int y = found(b);
if(x != y)
pre[y] = x;
}
void Tarjan(int u)
{
vis[u] = 1;
ance[u] = pre[u] = u;
for(int i = head[u]; ~i; i = a[i].pre)
{
int v = a[i].v;
int w = a[i].w;
if(!vis[v])
{
dis[v] = dis[u] + w;
Tarjan(v);
unite(u, v);//Tarjan完了再unite，保证了LCA是准确的
}
}
for(int i = qhead[u]; ~i; i = q[i].pre)
{
int v = q[i].v;
if(vis[v])//v是已经遍历过的非叶子节点
q[i].lca = q[i ^ 1].lca = ance[found(v)];
}
}
void init()
{
cnt = qcnt = 0;//从零开始，小偶大奇，异或1
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
memset(head, -1, sizeof(head));
memset(qhead, -1, sizeof(qhead));
}
int main()
{
int _;
scanf("%d", &_);
while(_--)
{
init();
scanf("%d%d", &n, &m);
int u, v, w;
for(int i = 0; i < n - 1; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add_adge(u, v, w);
add_adge(v, u, w);
}
for(int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
add_query(u, v);
add_query(v, u);
}
dis[1] = 0;
Tarjan(1);
for(int i = 0; i < m; ++i)//0 1/2 3/4 5/...取前者
{
int u = q[i * 2].u;
int v = q[i * 2].v;
int lca = q[i * 2].lca;
cout << dis[u] + dis[v] - 2 * dis[lca] << '\n';
}
}
return 0;
}
在建树的时候就把LCA求出来