- 科技
- LCA
BB
众所周知，LCA有N种方法。一种种慢慢学。。。
方法
1. 倍增求法
2. 待续…
Problem List
POJ 1986
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=4e4+5;
struct Edge
{
int to
;
int len
;
};
vector
<Edge
> G
[maxn
];
int fa
[maxn
][21],dep
[maxn
],dist
[maxn
];
void dfs(int u
)
{
for(int i
=1;(1<<i
)<=dep
[u
];i
++) fa
[u
][i
]=fa
[fa
[u
][i
-1]][i
-1];
for(int i
=0;i
<G
[u
].size();i
++)
{
Edge
&e
=G
[u
][i
];
if(e
.to
==fa
[u
][0])continue;
dep
[e
.to
]=dep
[u
]+1;
dist
[e
.to
]=dist
[u
]+e
.len
;
fa
[e
.to
][0]=u
;
dfs(e
.to
);
}
}
int lca(int x
,int y
)
{
if(dep
[x
]>dep
[y
])swap(x
,y
);
int f
=dep
[y
]-dep
[x
];
for(int i
=0;(1<<i
)<=f
;i
++)
if((1<<i
)&f
)y
=fa
[y
][i
];
if(y
==x
)return x
;
for(int i
=20;i
>=0;i
--)
if(fa
[x
][i
]!=fa
[y
][i
])
{
x
=fa
[x
][i
];
y
=fa
[y
][i
];
}
return fa
[x
][0];
}
int main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
int x
,y
,l
;
char c
;
for(int i
=0;i
<m
;i
++)
{
getchar();
scanf("%d %d %d %c",&x
,&y
,&l
,&c
);
G
[x
].push_back({y
,l
});
G
[y
].push_back({x
,l
});
}
dfs(1);
int k
;
scanf("%d",&k
);
while(k
--)
{
scanf("%d%d",&x
,&y
);
printf("%d\n",dist
[x
]+dist
[y
]-2*dist
[lca(x
,y
)]);
}
}
