http://poj.org/problem?id=1330
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
class LCA { ///最近公共祖先 build_o(n*logn) query_o(1)
typedef int typec;///边权的类型
static const int ME=2e4+;///边的个数
static const int MV=1e4+;///点的个数
static const int MR=MV<<;///rmq的个数
struct E {
int v,next;
typec w;
} e[ME];
int le,head[MV],H[MV],dex[MR],aa[MR],bb[MR],raa[MR][],rbb[MR][],Index;
typec dist[MV];
void init_dex() {
dex[]=-;
for(int i=; i<MR; i++) {
dex[i]=dex[i>>]+;
}
}
void dfs(int u,int fa,int level) {
aa[Index]=u;
bb[Index++]=level;
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if(v==fa) continue;
dist[v]=dist[u]+e[i].w;
dfs(v,u,level+);
aa[Index]=u;
bb[Index++]=level;
}
}
public:
LCA() { init_dex();};
void init() {
le=Index=;
mt(head,-);
}
void add(int u,int v,typec w) {
e[le].v=v;
e[le].w=w;
e[le].next=head[u];
head[u]=le++;
}
void build(int root) {
dist[root]=;
dfs(root,-,);
mt(H,-);
mt(rbb,0x3f);
for(int i=; i<Index; i++) {
int tmp=aa[i];
if(H[tmp]==-) H[tmp]=i;
rbb[i][]=bb[i];
raa[i][]=aa[i];
}
for(int i=; (<<i)<=Index; i++) {
for(int j=; j+(<<i)<Index; j++) {
int next=j+(<<(i-));
if(rbb[j][i-]<=rbb[next][i-]) {
rbb[j][i]=rbb[j][i-];
raa[j][i]=raa[j][i-];
} else {
rbb[j][i]=rbb[next][i-];
raa[j][i]=raa[next][i-];
}
}
}
}
int query(int l,int r) {
l=H[l];
r=H[r];
if(l>r) swap(l,r);
int p=dex[r-l+];
r-=(<<p)-;
return rbb[l][p]<=rbb[r][p]?raa[l][p]:raa[r][p];
}
typec getdist(int l,int r) {
return dist[l]+dist[r]-*dist[query(l,r)];
}
} gx; const int M=1e4+;
int du[M];
int main() {
int t,n,u,v;
while(~scanf("%d",&t)) {
while(t--) {
scanf("%d",&n);
gx.init();
mt(du,);
for(int i=; i<n; i++) {
scanf("%d%d",&u,&v);
du[v]++;
gx.add(u,v,);
gx.add(v,u,);
}
int rt=;
for(int i=; i<=n; i++) {
if(du[i]==) {
rt=i;
break;
}
}
gx.build(rt);
scanf("%d%d",&u,&v);
printf("%d\n",gx.query(u,v));
}
}
return ;
}
http://poj.org/problem?id=1470
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int res=;
char tmp;
while(!isdigit(tmp=getchar()));
do{
res=(res<<)+(res<<)+tmp-'';
}while(isdigit(tmp=getchar()));
return res;
} class LCA { ///最近公共祖先 build_o(n*logn) query_o(1)
typedef int typec;///边权的类型
static const int ME=2e3+;///边的个数
static const int MV=1e3+;///点的个数
static const int MR=MV<<;///rmq的个数
struct E {
int v,next;
typec w;
} e[ME];
int le,head[MV],H[MV],dex[MR],aa[MR],bb[MR],raa[MR][],rbb[MR][],Index;
typec dist[MV];
void init_dex() {
dex[]=-;
for(int i=; i<MR; i++) {
dex[i]=dex[i>>]+;
}
}
void dfs(int u,int fa,int level) {
aa[Index]=u;
bb[Index++]=level;
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if(v==fa) continue;
dist[v]=dist[u]+e[i].w;
dfs(v,u,level+);
aa[Index]=u;
bb[Index++]=level;
}
}
public:
LCA() {
init_dex();
};
void init() {
le=Index=;
mt(head,-);
}
void add(int u,int v,typec w) {
e[le].v=v;
e[le].w=w;
e[le].next=head[u];
head[u]=le++;
}
void build(int root) {///传入树根
dist[root]=;
dfs(root,-,);
mt(H,-);
mt(rbb,0x3f);
for(int i=; i<Index; i++) {
int tmp=aa[i];
if(H[tmp]==-) H[tmp]=i;
rbb[i][]=bb[i];
raa[i][]=aa[i];
}
for(int i=; (<<i)<=Index; i++) {
for(int j=; j+(<<i)<Index; j++) {
int next=j+(<<(i-));
if(rbb[j][i-]<=rbb[next][i-]) {
rbb[j][i]=rbb[j][i-];
raa[j][i]=raa[j][i-];
} else {
rbb[j][i]=rbb[next][i-];
raa[j][i]=raa[next][i-];
}
}
}
}
int query(int l,int r) {///查lca
l=H[l];
r=H[r];
if(l>r) swap(l,r);
int p=dex[r-l+];
r-=(<<p)-;
return rbb[l][p]<=rbb[r][p]?raa[l][p]:raa[r][p];
}
typec getdist(int l,int r) {///查两点最短距离
return dist[l]+dist[r]-*dist[query(l,r)];
}
} g; int ans[];
int du[];
int main(){
int n,m,u,v;
while(~scanf("%d",&n)){
g.init();
mt(du,);
for(int i=;i<n;i++){
u=getint();
m=getint();
while(m--){
v=getint();
du[v]++;
g.add(u,v,);
g.add(v,u,);
}
}
int root=;
for(int i=;i<=n;i++){
if(du[i]==){
root=i;
break;
}
}
g.build(root);
m=getint();
mt(ans,);
// printf("m=%d\n",m);
for(int i=;i<m;i++){
u=getint();
v=getint();
// printf("u=%d v=%d\n",u,v);
ans[g.query(u,v)]++;
// printf("m=%d\n",m);
}
// puts("out");
for(int i=;i<=n;i++){
if(ans[i]){
printf("%d:%d\n",i,ans[i]);
}
} }
return ;
}
http://poj.org/problem?id=1986
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
//const int M=100010;
class LCA { ///最近公共祖先 build_o(n*logn) query_o(1)
typedef int typec;///边权的类型
static const int ME=2e5+;///边的个数
static const int MV=1e5+;///点的个数
static const int MR=MV<<;///rmq的个数
struct E {
int v,next;
typec w;
} e[ME];
int le,head[MV],H[MV],dex[MR],aa[MR],bb[MR],raa[MR][],rbb[MR][],Index;
typec dist[MV];
void init_dex() {
dex[]=-;
for(int i=; i<MR; i++) {
dex[i]=dex[i>>]+;
}
}
void dfs(int u,int fa,int level) {
aa[Index]=u;
bb[Index++]=level;
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if(v==fa) continue;
dist[v]=dist[u]+e[i].w;
dfs(v,u,level+);
aa[Index]=u;
bb[Index++]=level;
}
}
public:
LCA() {
init_dex();
};
void init() {
le=Index=;
mt(head,-);
}
void add(int u,int v,typec w) {
e[le].v=v;
e[le].w=w;
e[le].next=head[u];
head[u]=le++;
}
void build(int root) {///传入树根
dist[root]=;
dfs(root,-,);
mt(H,-);
mt(rbb,0x3f);
for(int i=; i<Index; i++) {
int tmp=aa[i];
if(H[tmp]==-) H[tmp]=i;
rbb[i][]=bb[i];
raa[i][]=aa[i];
}
for(int i=; (<<i)<=Index; i++) {
for(int j=; j+(<<i)<Index; j++) {
int next=j+(<<(i-));
if(rbb[j][i-]<=rbb[next][i-]) {
rbb[j][i]=rbb[j][i-];
raa[j][i]=raa[j][i-];
} else {
rbb[j][i]=rbb[next][i-];
raa[j][i]=raa[next][i-];
}
}
}
}
int query(int l,int r) {///查lca
l=H[l];
r=H[r];
if(l>r) swap(l,r);
int p=dex[r-l+];
r-=(<<p)-;
return rbb[l][p]<=rbb[r][p]?raa[l][p]:raa[r][p];
}
typec getdist(int l,int r) {///查两点最短距离
return dist[l]+dist[r]-*dist[query(l,r)];
}
} gx; #include<cctype>
int getint(){
int res=;
char tmp;
while(!isdigit(tmp=getchar()));
do{
res=(res<<)+(res<<)+tmp-'';
}while(isdigit(tmp=getchar()));
return res;
}
int main(){
int n,m,x,y,z;
char op[];
while(~scanf("%d%d",&n,&m)){
gx.init();
while(m--){
// scanf("%d%d%d%s",&x,&y,&z,op);
x=getint();
y=getint();
z=getint();
gx.add(x,y,z);
gx.add(y,x,z);
}
// scanf("%d",&m);
m=getint();
gx.build();
while(m--){
// scanf("%d%d",&x,&y);
x=getint();
y=getint();
printf("%d\n",gx.getdist(x,y));
}
}
return ;
}
end