POJ - 3264 题意：给n个数，求区间(l,r)最大值与最小值之差。 RMQ板子题。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int maxn=50010; int h[maxn]; int mn[maxn][17],mx[maxn][17]; int n,q; void init() { int m=floor(log((double)n)/log(2.0)); for(int i=1;i<=n;i++) mn[i][0]=mx[i][0]=h[i]; for(int i=1;i<=m;i++){ for(int j=n;j>0;j--){ mx[j][i]=mx[j][i-1]; mn[j][i]=mn[j][i-1]; if(j+(1<<(i-1))<=n){ mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]); mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]); } } } } int rmq(int l,int r) { int m=floor(log((double)(r-l+1))/log(2.0)); return max(mx[l][m],mx[r-(1<<m)+1][m])-min(mn[l][m],mn[r-(1<<m)+1][m]); } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&h[i]); init(); while(q--){ int l,r; scanf("%d%d",&l,&r); printf("%d\n",rmq(l,r)); } return 0; }POJ - 1986 题意：求树上任意两点距离和 在线做法： dis(u,v)=dis[u]+dis[v]-dis[lca(u,v)] dfs构造欧拉序，由于u和v最近祖先（第一次出现）的时间戳是最小的，我们可以用st表来寻找公共祖先。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int maxn=40010;// int head[maxn],tot,cnt,tt; struct edge{ int v,w,nxt; }e[maxn*2]; int n,m,q; void init() { memset(head,-1,sizeof(head)); tot=0; tt=cnt=0; } void addedge(int u,int v,int w) { e[tot].v=v;e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++; } int dfn[maxn*2],p[maxn],f[maxn*2];// int dis[maxn],mn[maxn*2][17]; void dfs(int u,int fa) { int tmp=++tt;//时间戳 dfn[++cnt]=tmp;p[u]=cnt;f[tmp]=u;//f[]首次时间对应结点 p[]结点首次出现位置 for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v,w=e[i].w; if(v==fa) continue; dis[v]=dis[u]+w; dfs(v,u); dfn[++cnt]=tmp; } } void init(int n) { int m=floor(log((double)n)/log(2.0)); for(int i=1;i<=n;i++) mn[i][0]=dfn[i]; for(int i=1;i<=m;i++){ for(int j=n;j>0;j--){ mn[j][i]=mn[j][i-1]; if(j+(1<<(i-1))<=n){ mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]); } } } } int rmq(int l,int r) { int m=floor(log((double)(r-l+1))/log(2.0)); return min(mn[l][m],mn[r-(1<<m)+1][m]); } int lca(int u,int v) { if(p[u]>p[v]) swap(u,v); int k=rmq(p[u],p[v]); return f[k]; } int main() { init(); scanf("%d%d",&n,&m); int u,v,w; char s[4]; for(int i=1;i<=m;i++){ scanf("%d%d%d%s",&u,&v,&w,s); addedge(u,v,w); addedge(v,u,w); } dis[1]=0; dfs(1,-1); //for(int i=1;i<=n;i++) printf("dis[%d]:%d\n",i,dis[i]); init(cnt); scanf("%d",&q); while(q--){ int l,r; scanf("%d%d",&u,&v); printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]); } return 0; }在线做法2，并查集查找公共祖先。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int maxn=40010; int tot,head[maxn]; struct edge{ int v,w,nxt; }e[maxn*2]; int tot2,head2[maxn]; struct query{ int v,nxt,id; }q[maxn]; int n,m,qq; bool vis[maxn]; int dis[maxn],ans[maxn]; void init() { tot=tot2=0; memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); memset(vis,0,sizeof(vis)); } void addedge(int u,int v,int w) { e[tot].v=v;e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++; } void addquery(int u,int v,int id) { q[tot2].v=v; q[tot2].id=id; q[tot2].nxt=head2[u]; head2[u]=tot2++; } int f[maxn]; int find1(int x) { return x==f[x]?x:f[x]=find1(f[x]); } void dfs(int u,int fa) { //printf("u:%d fa:%d\n",u,fa); f[u]=u; for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v,w=e[i].w; if(v==fa) continue; dis[v]=dis[u]+w; dfs(v,u); f[v]=u; } vis[u]=1;// for(int i=head2[u];~i;i=q[i].nxt){ int v=q[i].v,id=q[i].id; if(vis[v]) ans[id]=dis[u]+dis[v]-2*dis[find1(v)];// find1(v)ÊÇuºÍv¹«¹²×æÏÈ } } int main() { init(); scanf("%d%d",&n,&m); char s[4]; int u,v,w; for(int i=0;i<m;i++){ scanf("%d%d%d%s",&u,&v,&w,s); addedge(u,v,w); addedge(v,u,w); } scanf("%d",&qq); for(int i=0;i<qq;i++){ scanf("%d%d",&u,&v); addquery(u,v,i); addquery(v,u,i); } dis[1]=0; dfs(1,1); for(int i=0;i<qq;i++) printf("%d\n",ans[i]); }HYSBZ - 1787 给一颗树，求树上3个结点的最近公共点 题解：3个结点可以得到3个lca，我们取深度最大的那个，就是我们要的最近公共点。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int maxn=500010; int head[maxn],tot,cnt,tt; struct edge{ int v,w,nxt; }e[maxn*2]; int n,m,q; void init() { memset(head,-1,sizeof(head)); tot=0; tt=cnt=0; } void addedge(int u,int v,int w) { e[tot].v=v;e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++; } int dfn[maxn*2],p[maxn],f[maxn*2]; int dis[maxn],mn[maxn*2][20]; int d[maxn]; void dfs(int u,int fa,int deep) { int tmp=++tt;//时间戳 d[u]=deep; dfn[++cnt]=tmp;p[u]=cnt;f[tmp]=u;//f[]首次时间对应结点 p[]结点首次出现位置 for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v,w=e[i].w; if(v==fa) continue; dis[v]=dis[u]+w; dfs(v,u,deep+1); dfn[++cnt]=tmp; } } void init(int n) { int m=floor(log((double)n)/log(2.0)); for(int i=1;i<=n;i++) mn[i][0]=dfn[i]; for(int i=1;i<=m;i++){ for(int j=n;j>0;j--){ mn[j][i]=mn[j][i-1]; if(j+(1<<(i-1))<=n){ mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]); } } } } int rmq(int l,int r) { int m=floor(log((double)(r-l+1))/log(2.0)); return min(mn[l][m],mn[r-(1<<m)+1][m]); } int lca(int u,int v) { if(p[u]>p[v]) swap(u,v); int k=rmq(p[u],p[v]); return f[k]; } int main() { init(); scanf("%d%d",&n,&m); int u,v,w,x,y,z,ans; int rt; for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); addedge(u,v,1); addedge(v,u,1); } dis[1]=0; dfs(1,-1,1); //for(int i=1;i<=n;i++) printf("dis[%d]:%d\n",i,dis[i]); init(cnt); while(m--){ scanf("%d%d%d",&u,&v,&w); y=lca(u,v); z=lca(w,v); x=lca(u,w); if(d[y]>=d[z]&&d[y]>=d[x]) rt=y,ans=dis[u]+dis[v]-2*dis[y]+dis[w]+dis[y]-2*dis[lca(w,y)]; else if(d[z]>=d[y]&&d[z]>=d[x]) rt=z,ans=dis[w]+dis[v]-2*dis[z]+dis[u]+dis[z]-2*dis[lca(u,z)]; else rt=x,ans=dis[u]+dis[w]-2*dis[x]+dis[v]+dis[x]-2*dis[lca(v,x)]; printf("%d %d\n",rt,ans); } return 0; }UVA - 11354 题意：n个点，m条边，q个查询，求u到v的所有路径中，最小的路径最大边，（也有个叫法，是u到v的最小瓶颈路）。 题解：有个结论，u到v的最小瓶颈路，一定在最小生成树上。我们先求出最小生成树，再用倍增算法求解。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=500010;// const int maxm=100010*2; int n,m,q; //并查集 struct edge1{ int u,v,w; }e1[maxm]; int tot; void addedge1(int u,int v,int w) { e1[tot].u=u; e1[tot].v=v; e1[tot++].w=w; } bool cmp(const edge1 &a,const edge1 &b) { return a.w<b.w; } int f[maxn]; int find1(int x) { return x==f[x]?x:f[x]=find1(f[x]); } bool union1(int x,int y) { int fx=find1(x),fy=find1(y); if(fx!=fy){ f[fx]=fy; return true; } return false; } struct edge{ int v,w,nxt; }e[maxm]; int head[maxn]; int deep[maxn],p[maxn][22],mx[maxn][22]; void init() { memset(head,-1,sizeof(head)); tot=0; memset(p,0,sizeof(p)); memset(mx,0,sizeof(mx)); } void addedge(int u,int v,int w) { e[tot].v=v;e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++; } //倍增求最近公共祖先，并保存路径最大值 void dfs(int u,int fa,int d) { deep[u]=d; for(int i=1;i<20;i++){ p[u][i]=p[p[u][i-1]][i-1]; mx[u][i]=max(mx[u][i-1],mx[p[u][i-1]][i-1]); } for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v; if(v==fa) continue; p[v][0]=u; mx[v][0]=e[i].w; dfs(v,u,d+1); } } int cal(int u,int v) { int ans=0; if(deep[u]<deep[v]) swap(u,v); int h=deep[u]-deep[v]; for(int i=0;i<20;i++){ if((1<<i)&h){ ans=max(ans,mx[u][i]); u=p[u][i]; } } if(u!=v){ for(int i=19;i>=0;i--){ if(p[u][i]!=p[v][i]){ ans=max(ans,max(mx[u][i],mx[v][i])); u=p[u][i]; v=p[v][i]; } } ans=max(ans,max(mx[u][0],mx[v][0]));// } return ans; } int main() { bool ff=0; while(~scanf("%d%d",&n,&m)){ if(ff) printf("\n"); ff=1; int u,v,w; tot=0; while(m--){ scanf("%d%d%d",&u,&v,&w); addedge1(u,v,w); } for(int i=1;i<=n;i++){ f[i]=i; } m=tot; init(); sort(e1,e1+m,cmp); for(int i=0;i<m;i++){ u=e1[i].u;v=e1[i].v; w=e1[i].w; if(union1(u,v)){ addedge(u,v,w); addedge(v,u,w); } } p[1][0]=1; dfs(1,-1,1); scanf("%d",&q); while(q--){ scanf("%d%d",&u,&v); printf("%d\n",cal(u,v)); } } return 0; }