第一题： POJ 1330 Nearest Common Ancestors POJ 1330
这个题可不是以1为根节点，不看题就会一直wa呀；
加一个找根节点的措施；
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
#define N 50010
using namespace std;
int f[N][],d[N],dist[N],lin[N*],b[N],root;
inline int read() {
int s = , w = ;
char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -; ch = getchar(); }
while (isdigit(ch)) { s = (s << ) + (s << ) + (ch ^ ); ch = getchar(); }
return s * w;
}
struct gg
{
int y,v,next;
}a[N<<];
int T,n,m,tot,t;
queue<int> q;
void add(int x,int y)
{
a[++tot].y=y;
a[tot].next=lin[x];
lin[x]=tot;
}
void bfs(int x)
{
q.push(x);d[x]=;
while(q.size())
{
int x=q.front();q.pop();
for(int i=lin[x];i;i=a[i].next)
{
int y=a[i].y;
if(d[y]) continue;
d[y]=d[x]+;
f[y][]=x;
for(int j=;j<=t;j++)
f[y][j]=f[f[y][j-]][j-];
q.push(y);
}
}
}
int lca(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;i--)
if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=t;i>=;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][];
}
int main()
{
T=read();
while(T--)
{
memset(b,,sizeof(b));
memset(f,,sizeof(f));
queue<int> q;
n=read();
t=(int)(log(n)/log())+;
for(int i=;i<=n;i++) lin[i]=d[i]=;
tot=;
for(int i=;i<n;i++)
{
int x,y,z;
x=read();y=read();
b[y]++;
add(x,y);
}
for(int i=;i<=n;i++)
{
if(b[i]==)
{
root=i;
break;
}
}
bfs(root);
int x,y;
x=read();y=read();
cout<<lca(x,y)<<endl;
}
return ;
}
第二题：HDU 2586
加了边权的lca模板；
关键最近距离为dis【i】+dis【j】-2*dis【lca（x，y）】；
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype> #define N 50010
using namespace std;
int f[N][],d[N],dist[N],lin[N*];
inline int read() {
int s = , w = ;
char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -; ch = getchar(); }
while (isdigit(ch)) { s = (s << ) + (s << ) + (ch ^ ); ch = getchar(); }
return s * w;
}
struct gg
{
int y,v,next;
}a[N<<];
int T,n,m,tot,t;
queue<int> q;
void add(int x,int y,int z)
{
a[++tot].y=y;
a[tot].next=lin[x];
lin[x]=tot;
a[tot].v=z;
} void bfs()
{
q.push();d[]=;
while(q.size())
{
int x=q.front();q.pop();
for(int i=lin[x];i;i=a[i].next)
{
int y=a[i].y;
if(d[y]) continue;
d[y]=d[x]+;
dist[y]=dist[x]+a[i].v;
f[y][]=x;
for(int j=;j<=t;j++)
f[y][j]=f[f[y][j-]][j-];
q.push(y);
}
}
}
int lca(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;i--)
if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=t;i>=;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][];
}
int main()
{
T=read();
while(T--)
{
queue<int> q;
n=read();m=read();
t=(int)(log(n)/log())+;
for(int i=;i<=n;i++) lin[i]=d[i]=;
tot=;
for(int i=;i<n;i++)
{
int x,y,z;
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
bfs();
for(int i=;i<=m;i++)
{
int x,y;
x=read();y=read();
cout<<dist[x]+dist[y]-*dist[lca(x,y)]<<endl;
} }
return ;
}
第三题：BZOJ 1787
对三个节点两两求LCA会有2种情况： 1 均相同:答案即为此LCA： 2 有1个LCA与其他的不同：答案为此LCA。
#include<bits/stdc++.h>
#define N 500001
using namespace std;
int f[N][],d[N],dist[N],lin[N*],ans;
inline int read() {
int s = , w = ;
char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -; ch = getchar(); }
while (isdigit(ch)) { s = (s << ) + (s << ) + (ch ^ ); ch = getchar(); }
return s * w;
}
struct gg
{
int y,v,next;
}a[N<<];
int T,n,m,tot,t;
queue<int> q;
void add(int x,int y)
{
a[++tot].y=y;
a[tot].next=lin[x];
lin[x]=tot;
} void bfs()
{
q.push();d[]=;
while(q.size())
{
int x=q.front();q.pop();
for(int i=lin[x];i;i=a[i].next)
{
int y=a[i].y;
if(d[y]) continue;
d[y]=d[x]+;
f[y][]=x;
for(int j=;j<=t;j++)
f[y][j]=f[f[y][j-]][j-];
q.push(y);
}
}
}
int lca(int x,int y)
{
ans=;
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;i--)
if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=t;i>=;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return ans=f[x][];
}
int dis(int x,int y)
{
int t=lca(x,y);
return d[x]+d[y]-*d[t];
}
int main()
{
queue<int> q;
n=read();m=read();
t=(int)(log(n)/log())+;
for(int i=;i<=n;i++) lin[i]=d[i]=;
tot=;
for(int i=;i<n;i++)
{
int x,y;
x=read();y=read();
add(x,y);add(y,x);
}
bfs();
for(int i=;i<=m;i++)
{
int x,y,z;
x=read();y=read();z=read();
int xx,yy,zz;
int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z),t;
if(p1==p2) t=p3;
else if(p2==p3) t=p1;
else t=p2;
int ans=dis(x,t)+dis(y,t)+dis(z,t);
cout<<t<<' '<<ans<<endl;
}
return ;
}
来自石神的代码；跑的很快，推荐；
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+;
const int inf=0x7fffffff;
template<typename T>inline void read(T &x)
{
x=;
T f=,ch=getchar();
while (!isdigit(ch)) ch=getchar();
if (ch=='-') f=-, ch=getchar();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
x*=f;
}
int ver[maxn<<],Next[maxn<<],head[maxn],len;
inline void add(int x,int y)
{
ver[++len]=y,Next[len]=head[x],head[x]=len;
}
queue<int>q;
int d[maxn],f[maxn][],vis[maxn],t;
inline void bfs(int root)
{
q.push(root);
d[root]=;
while (!q.empty())
{
int x=q.front();
q.pop();
for (int i=head[x];i;i=Next[i])
{
int y=ver[i];
if (d[y]) continue;
d[y]=d[x]+;
f[y][]=x;
for (int j=;j<=t;++j)
f[y][j]=f[f[y][j-]][j-];
q.push(y);
}
}
}
inline int lca(int x,int y)
{
if (d[x]>d[y]) swap(x,y);
for (int i=t;i>=;--i)
if (d[f[y][i]]>=d[x]) y=f[y][i];
if (x==y) return x;
for (int i=t;i>=;--i)
if (f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][];
}
int main()
{
int n,m,id,ans;read(n);read(m);
t=log2(n*1.0);
memset(d,,sizeof(d));
memset(f,,sizeof(f));
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));
len=;
for (int i=;i<n;++i)
{
int x,y;read(x);read(y);
add(x,y);add(y,x);
}
bfs();
for (int i=;i<=m;++i)
{
int x,y,z;read(x);read(y);read(z);
int l1=lca(x,y),l2=lca(x,z),l3=lca(y,z),ans=inf,tmp,id;
int q1=lca(l1,z),q2=lca(l2,y),q3=lca(l3,x);
tmp=d[x]+d[y]-d[l1]+d[z]-(d[q1]<<);
if (tmp<ans)
ans=tmp,id=l1;
tmp=d[x]+d[z]-d[l2]+d[y]-(d[q2]<<);
if (tmp<ans)
ans=tmp,id=l2;
tmp=d[y]+d[z]-d[l3]+d[x]-(d[q3]<<);
if (tmp<ans)
ans=tmp,id=l3;
printf("%d %d\n",id,ans);
}
return ;
}
第四题：UVA11354 Bond
一类例题：LUOGU UVA 11354 最小生成树+倍增求LCA
NOIP 2013 货车运输 最大生成树+倍增求LCA
这个题：最小瓶颈树。 倍增维护边权最大值。
一份代码解决两个问题，代码注释的代码改一改；
#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+;
const int inf=0x3f3f3f3f;
template<typename T>inline void read(T &x)
{
x=;
T f=,ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-, ch=getchar();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
x*=f;
}
struct Edge
{
int x,y,z,next;
}G[maxn<<],A[maxn<<];//G[]是最大生成树的图
int n,m,head[maxn],len;
inline void add(int x,int y,int z)
{
G[++len].y=y,G[len].z=z,G[len].next=head[x],head[x]=len;
}
int fa[maxn];
inline int get(int x)
{
if (x==fa[x]) return x;
return fa[x]=get(fa[x]);
}
inline bool cmp(Edge a,Edge b)
{
// return a.z>b.z;
return a.z<b.z;
}
inline void Kruskal()
{
sort(A+,A+m+,cmp);
for (int i=;i<=n;++i)
fa[i]=i;
for (int i=;i<=m;++i)
{
int x=get(A[i].x),y=get(A[i].y);
if (x!=y)
{
fa[y]=x;
add(A[i].x,A[i].y,A[i].z);
add(A[i].y,A[i].x,A[i].z);
}
}
}
int d[maxn],f[maxn][],w[maxn][];//fa[]表示并查集中的父节点，f[][]表示树上的父节点，w[][]表示最大载重
inline void dfs(int x)
{
for (int i=;i<=;++i)//LCA初始化
{
f[x][i]=f[f[x][i-]][i-];
// w[x][i]=min(w[x][i-1],w[f[x][i-1]][i-1]);
w[x][i]=max(w[x][i-],w[f[x][i-]][i-]);
}
for (int i=head[x];i;i=G[i].next)
{
int y=G[i].y;
if (d[y]) continue;
d[y]=d[x]+;//计算深度
f[y][]=x;//储存父节点
w[y][]=G[i].z;//储存到父节点的权值
dfs(y);
}
}
inline int lca(int x, int y)
{
if (get(x)!=get(y)) return -;//不连通，输出-1
// int ans=inf;
int ans=;
if (d[x]>d[y]) swap(x,y);//保证y节点更深
for (int i=;i>=;--i)//将y节点上提到于x节点相同深度
if (d[f[y][i]]>=d[x])
{
// ans=min(ans,w[y][i]);//更新最大载重（最小边权）
ans=max(ans,w[y][i]);
y=f[y][i];//修改y位置
}
if (x==y) return ans;//如果位置已经相等，直接返回答案
for (int i=;i>=;--i)//寻找公共祖先
if (f[x][i]!=f[y][i])
{
// ans=min(ans,min(w[x][i], w[y][i]));//更新最大载重（最小边权）
ans=max(ans,max(w[x][i],w[y][i]));
x=f[x][i],y=f[y][i];//修改x,y位置
}
// ans=min(ans,min(w[x][0],w[y][0]));//更新此时x,y到公共祖先最大载重，f[x][0], f[y][0]即为公共祖先
ans=max(ans,max(w[x][],w[y][]));
return ans;
}
int main()
{
int flag=;
while (scanf("%d %d",&n,&m)!=EOF)
{
if (flag) printf("\n");
else flag=;
memset(f,,sizeof(f));
memset(w,,sizeof(w));
memset(d,,sizeof(d));
memset(head,,sizeof(head));
len=;
for (int i=;i<=m;++i)
read(A[i].x),read(A[i].y),read(A[i].z);
Kruskal();
for (int i=;i<=n;++i)//dfs收集信息
if (!d[i])
{
d[i]=;
dfs(i);
f[i][]=i;
// w[i][0]=inf;
w[i][]=-inf;
}
int q;
read(q);
while (q--)
{
int x,y;
read(x);read(y);
printf("%d\n",lca(x,y));
}
}
return ;
}
第五题：BZOJ 1977 【模板】严格次小生成树[BJWC2010]
先求一次最小生成树，然后枚举哪些非树边，找到以非树边两端点 在树上路径中最大的一条边，将这条边加入树，形成一个环，那么删掉 此环上的一条边，就会从新出现一棵生成树。
如何高效的去找要删去的边？
倍增LCA 倍增维护3个值，father维护LCA，f 维护路径上的最大值，g维护路 径上的严格次大值。
对于删环上的边，如果添加进来的边与环上最大值不同，那么直接 删换上最大值，如果与最大值相同，就必须删次大值。
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define N 100001
#define M 300001
#define inf 0x7fffffff
#define ll long long
using namespace std;
int n,m,tot,cnt,mn=inf;
ll ans;
int father[N],lin[N],deep[N],f[N][],d1[N][],d2[N][];
inline int read() {
int s = , w = ;
char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -; ch = getchar(); }
while (isdigit(ch)) { s = (s << ) + (s << ) + (ch ^ ); ch = getchar(); }
return s * w;
}
void put(int x)
{
if(x==){putchar('');putchar('\n');return;}
if(x<){putchar('-');x=-x;}
int num=;char ch[];
while(x) ch[++num]=x%+'',x/=;
while(num) putchar(ch[num--]);
putchar('\n');
}
struct data {
int x,y,v;
bool bl;
} a[M];
struct edge {
int to,next,v;
} e[N*];
bool cmp(data a,data b) {
return a.v<b.v;
}
void add(int u,int v,int w) {
e[++cnt].to=v;
e[cnt].next=lin[u];
e[cnt].v=w;
lin[u]=cnt;
}
int find(int x) {
return x==father[x]?x:find(father[x]);
}
void dfs(int x,int fs) {
for(int i=; i<=; i++) {
if(deep[x]<(<<i)) break;
f[x][i]=f[f[x][i-]][i-];
d1[x][i]=max(d1[x][i-],d1[f[x][i-]][i-]);
if(d1[x][i-]==d1[f[x][i-]][i-])
d2[x][i]=max(d2[x][i-],d2[f[x][i-]][i-]);
else {
d2[x][i]=min(d1[x][i-],d1[f[x][i-]][i-]);
d2[x][i]=max(d2[x][i-],d2[x][i]);
d2[x][i]=max(d2[x][i],d2[f[x][i-]][i-]);
}
}
for(int i=lin[x]; i; i=e[i].next)
if(e[i].to!=fs) {
f[e[i].to][]=x;
d1[e[i].to][]=e[i].v;
deep[e[i].to]=deep[x]+;
dfs(e[i].to,x);
}
}
int lca(int x,int y) {
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=; i<=; i++)
if((<<i)&t)x=f[x][i];
for(int i=; i>=; i--) {
if(f[x][i]!=f[y][i]) {
x=f[x][i];
y=f[y][i];
}
}
if(x==y)return x;
return f[x][];
}
void cal(int x,int fs,int v) {
int mx1=,mx2=;
int t=deep[x]-deep[fs];
for(int i=; i<=; i++) {
if(t&(<<i)) {
if(d1[x][i]>mx1) {
mx2=mx1;
mx1=d1[x][i];
}
mx2=max(mx2,d2[x][i]);
x=f[x][i];
}
}
if(mx1!=v)mn=min(mn,v-mx1);
else mn=min(mn,v-mx2);
}
void tp(int t,int v) {
int x=a[t].x,y=a[t].y,f=lca(x,y);
cal(x,f,v);
cal(y,f,v);
}
int main() {
n=read();m=read();
for(int i=; i<=n; i++)
father[i]=i;
for(int i=; i<=m; i++)
a[i].x=read(),a[i].y=read(),a[i].v=read();
sort(a+,a+m+,cmp);
for(int i=; i<=m; i++) {
int p=find(a[i].x),q=find(a[i].y);
if(p!=q) {
father[p]=q;
ans+=a[i].v;
a[i].bl=;
add(a[i].x,a[i].y,a[i].v);
add(a[i].y,a[i].x,a[i].v);
tot++;
if(tot==n-)break;
}
}
dfs(,);
for(int i=; i<=m; i++)
if(!a[i].bl) tp(i,a[i].v);
printf("%lld",ans+mn);
return ;
}
第六题：跳跳棋
为了方便研究跳法，我们把棋子按坐标大小排序后设为a, b, c。
每次都有三种跳法： 1 b往左跳 2 b往右跳 3 离b近的往里跳(远的不允许跳，会越过两个棋子)
从只有两种跳法的所有状态出发，就可以到达任意一种状态。
因为 两边往中间跳实际上是一种状态的还原。 对于每一个状态(x, y, z)：中间的向外面跳为(2x − y, x, z)或 者(x, z, 2z − y),设为左结点和右结点。
所以我们就可以把题意转化一下，即第一问为两种状态是否有lca， 而第二种则是问两种状态在树上的距离。我们可以采用类似倍增的方法 跳lca，来求出答案。
首先，我们应该判断两个状态可不可以互达。
要做到这一点，实际上就是看两个状态所在树的根是不是相同就行 了。
怎么样算出这个根呢？
令b − a = d1, c − b = d2,不妨设d1 < d2，那么a, b两点可以一直向 右，每次移动d1距离，直到d2 − k × d1 ≤ d1为止，这几乎是一个取模运 算。
1 d1|d2 : 最后剩下d1距离，移动d2|d1 − 1步。
2 剩下d2 mod d1距离，移动[d1\d2|
步。 而根据与其类似的辗转相除的过程的复杂度，这样计算的复杂度 是O(logd)的，这样就能很快算出根了。