题解 P2912 【[USACO08OCT]牧场散步Pasture Walking】

蒟蒻第一次写倍增。。。 这里简单说一下倍增的原理 任意一个正整数，都可以表示为几个2的n次幂之和。 根据这个原理，我们只需知道一个点上方的第2的n次方个祖先，就可以求出其所有祖先 （e。g。求第3个祖先可以表示为该点上方第二个祖先的第1个祖先） 同理，知道一个点上方的第2的n次方个祖先到该点的距离，即可求出该点到所有祖先的距离 那么，令father【i】【j】表示点i上方第2的j次方的祖先编号，d【i】【j】表示到father【i】【j】的距离 由2^n=2^(n-1)+2^(n-1）； 可得father【i】【j】=father【father【i】【j-1】】【j-1】；d【i】【j】=d【i】【j-1】+d【father【i】【j-1】】【j-1】； 上代码~ ```cpp #include<stdio.h> #include<algorithm> using namespace std; struct data//邻接表 { int next;int v;int val; }edge[2010];int cnt;int alist[1010]; void add(int u,int v,int val) { edge[++cnt].v=v; edge[cnt].val=val; edge[cnt].next=alist[u]; alist[u]=cnt;return; } int d[1010][15]; int father[1010][15]; int depth[1010];//深度数组，作用一会说 int n;int q; void dfs(int x)//深搜，完成祖先和祖先距离和深度关系 { for(int i=1;i<15;i++) { if(father[x][i-1]!=0)//递推f和d { father[x][i]=father[father[x][i-1]][i-1]; d[x][i]=d[x][i-1]+d[father[x][i-1]][i-1]; } else break;//0表示没有这个祖先，即距离太大了，那么更大的2^(n+1)也是0 } int next=alist[x]; while(next)//遍历出边 { int v=edge[next].v;int val=edge[next].val; if(v!=father[x][0])//显然不能爸爸是儿子的儿子，这就乱套了 { father[v][0]=x;//初始化儿子 d[v][0]=val;depth[v]=depth[x]+1; dfs(v); } next=edge[next].next; } return; } int lca(int u,int v)//标准的lca模板 { int res=0;//一定要赋值 if(depth[u]<depth[v])swap(u,v);//钦定u更低 int delta=depth[u]-depth[v]; for(int i=0;i<15;i++) { if(delta&(1<<i))//把depth【u】和depth【v】的差拆成2的n次幂之和 { res+=d[u][i];//更改u的同时更改d u=father[u][i];//更改u } } if(u==v)return res;//如果v是直系祖先，返回 for(int i=14;i>=0;i--)//先选大的二进制位，有点贪心的意思 { if(father[u][i]!=father[v][i])//移动 { res+=d[u][i]+d[v][i]; u=father[u][i]; v=father[v][i]; } } res+=d[u][0]+d[v][0];//最后father【u】【0】才是lca，因此加上u，v到lca距离 return res; } int main() { scanf("%d%d",&n,&q); for(int i=0;i<n-1;i++) { int u;int v;int val; scanf("%d%d%d",&u,&v,&val); add(u,v,val);//双向边 add(v,u,val); } dfs(1);//dfs for(int i=0;i<q;i++) { int u;int v; scanf("%d%d",&u,&v); printf("%d\n",lca(u,v));//处理询问 } return 0; } ```