小机房的树CODEVS 2370

————最近公共祖先和动态规划的完美结合

 【题目描述】

  小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力。

 【输入描述】

  第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。

  接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

 【输出描述】

  一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离

 【分析】

  求树上最短路，而且要求的是NlogN的算法，很容易能想到LCA，确实，LCA的确适合树上最短路

  Ps:LCA的具体内容博主的博客里有

 

  求出两点的LCA的过程中即可计算答案，我们设d(i,j)表示树上的i节点向上走2^j到达的节点所走的距离

  而d数组在初始化深度的时候即可计算

  时间复杂度O(NlogN)

  完美AC...

 【代码】

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int MaxN=100001; 8  9 struct list{10     int to,next,w;11 }e[MaxN];12 13 int head[MaxN],n,cnt=0;14 int deep[MaxN],p[MaxN][22],d[MaxN][22];//d(i,j)表示i到第2^j祖先的距离 15 int ans=0;16 17 void addedge(int u,int v,int w){18     cnt++;19     e[cnt].to=v;20     e[cnt].w=w;21     e[cnt].next=head[u];22     head[u]=cnt;23 }24 25 int lca(int u,int v){26     if(deep[u]
         
          =0;i--)34       if(p[u][i]!=p[v][i]){35           ans+=d[u][i]+d[v][i];36         u=p[u][i];37           v=p[v][i];38       }39     if(u!=v)ans+=d[u][0]+d[v][0];40     return ans;41 }42 43 void dfs(int u){44     int i;45     for(i=1;i<=21;i++){46       if(deep[u]<(1<
         
        
       
      
     

 

  无可否认，LCA的代码是有点长，但理解了还是很容易能敲出来的