/*
1
tarjan O(1)求lca
o
/ \ \
o o o
/\ /\ \
o o o o o
/\ y x 3
o o 2 1
第一类 已经遍历过,且回溯过[2]
o
/
o
/\ /
o o o
/\
o o
当前搜到了最右边这条路时
左边的分支上的点都是搜索过且回溯过的(标记为2)
第二类 正在搜索的分支[1] 标记为1
o
\
o
\
o
x
看x和第一类点中点的lca都是第一类中分支的根节点
那么可以把当前这条路上作为根节点的点中已经遍历过的分支合并到该根节点(用并查集做)
. .
/ \ \
o . .
/\ / → 回溯完到根节点后把根节点左边的子树上的点都用并查集合并到根节点
o o o
/\
o o
那么在遍历点x后 扫描所有和x相关的询问 如果询问中另一个点y已经被遍历+回溯过了
lca[x][y] = p[y]
o
/ \
o lca=p[y]
/\ /\
o o o o
/\ y x
o o
这样 枚举每个点1次 所有点合并1次 查询每个点1次 并查集O(1)
第三类 还未搜索过[0]
o
\
o
\
o
2
求树上两个点的距离
o
1/ \
lca o
2/\4 /\
o o o o
3/\ y
o o
x
d[node] 代表根节点到node的距离
其中d[x] = 1+2+3
d[y] = 1+4
则
x到y的距离 = d[x]+d[y] - 2*d[lca]
(3)Tarjan-离线求LCA O(m+n)
在深度优先遍历时,将所有点分成三大类
[1] 已经遍历过,且回溯过
[2] 正在搜索的分支
[3] 还未搜索到的点
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];//每个点和1号点的距离
int p[N];
int res[M];
int st[N];
vector<PII> query[N];//把询问存下来
// query[i][first][second] first存查询距离i的另外一个点j,second存查询编号idx
void add(int a,int b,int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
int find(int x)
{
if(p[x]!=x)p[x] = find(p[x]);
return p[x];
}
void dfs(int u,int fa)
{
for(int i=h[u];~i;i=ne[i])
{
int j = e[i];
if(j==fa) continue;
dist[j] = dist[u]+w[i];
dfs(j,u);
}
}
void tarjan(int u)
{
st[u]=1;//当前路径点标记为1
// u这条路上的根节点的左下的点用并查集合并到根节点
for(int i = h[u];~i;i=ne[i])
{
int j = e[i];
if(!st[j])
{
tarjan(j);//往左下搜
p[j] = u;//从左下回溯后把左下的点合并到根节点
}
}
// 对于当前点u 搜索所有和u
for(auto item:query[u])
{
int y = item.first,id = item.second;
if(st[y]==2)//如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2)
{
int anc = find(y);//y的根节点
// x到y的距离 = d[x]+d[y] - 2*d[lca]
res[id] = dist[u]+dist[y] - dist[anc]*2;//第idx次查询的结果 res[idx]
}
}
//点u已经搜索完且要回溯了 就把st[u]标记为2
st[u] = 2;
}
int main()
{
cin >> n >> m;
// 建图
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c),add(b,a,c);
}
// 存下询问
for(int i=0;i<m;i++)
{
int a,b;
cin >> a >> b;
if(a!=b)
{
query[a].push_back({b,i});
query[b].push_back({a,i});
}
}
for(int i=1;i<=n;i++)p[i] = i;
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++)cout << res[i] << '\n';//把每次询问的答案输出
return 0;
}
这里的dfs能不能在tarjan中同时进行呢,如果可以找到lca,证明两个点都被遍历过,可以算距离了?
当然可以了:
st数组不用标记成1或2,1和2是等价的。我代码也可以过
这个遍历不一定是 根节点的坐下的点 把
这个树的左边是人为定义的,就是先被遍历到的点
这里为啥是N = 10010不应该是N = 20010吗?
1w个点啊,为什么是2w个,2w个是边啊(无方向)
为什么要在回溯中令 p[j]=u,先进行这句不行吗
如果你先令 p[j]=u,
int anc = find(y);//y的根节点
这一行求的y的根节点就不对了