bzoj1602 / P2912 [USACO08OCT]牧场散步Pasture Walking（倍增lca）

求树上两点间路径--->lca
使用倍增处理lca（树剖多长鸭）
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cctype>

 #define re register

 using namespace std;

 char gc(){

     static char buf[],*p1=buf,*p2=buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

 }

 void read(int &x){

     char c=getchar();x=;

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

 }

 void swap(int &a,int &b){a^=b;b^=a;a^=b;}

 //-----优化------

 #define N 1002

 int n,Q,d[N],fa[][N],fv[][N];

 int cnt,hd[N],nxt[N<<],ed[N],poi[N<<],val[N<<];

 void adde(int x,int y,int v){

     nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt;

     ed[x]=cnt; poi[cnt]=y; val[cnt]=v;

 }

 void dfs(int x,int ffa){

     fa[][x]=ffa; d[x]=d[ffa]+;

     for(int i=;(<<i)<=d[x];++i){

         fa[i][x]=fa[i-][fa[i-][x]];

         fv[i][x]=fv[i-][x]+fv[i-][fa[i-][x]];//路径和预处理

     }

     for(int i=hd[x];i;i=nxt[i])

         if(poi[i]!=ffa){

             fv[][poi[i]]=val[i];

             dfs(poi[i],x);

         }

 }

 int ask(int x,int y){

     if(d[x]<d[y]) swap(x,y);

     int res=;

     for(int i=;i>=;--i)

         if(d[fa[i][x]]>=d[y])

             res+=fv[i][x],x=fa[i][x];

     if(x==y) return res;

     for(int i=;i>=;--i)

         if(fa[i][x]!=fa[i][y]){

             res+=fv[i][x]+fv[i][y];

             x=fa[i][x]; y=fa[i][y];

         }

     return res+fv[][x]+fv[][y];//记得最后还要加一次

 }

 int main(){

 //    freopen("chino.in","r",stdin);

     read(n);read(Q); int q1,q2,q3;

     for(re int i=;i<n;++i){

         read(q1);read(q2);read(q3);

         adde(q1,q2,q3); adde(q2,q1,q3);

     }dfs(,);

     for(re int i=;i<=Q;++i){

         read(q1); read(q2);

         printf("%d\n",ask(q1,q2));

     }return ;

 }