首页 > 代码库 > 小机房的树CODEVS 2370
小机房的树CODEVS 2370
小机房的树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 <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 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]<deep[v])swap(u,v);27 int t=deep[u]-deep[v],i,ans=0;28 for(i=0;i<=21;i++)29 if((1<<i)&t){30 ans+=d[u][i];31 u=p[u][i];32 }33 for(i=21;i>=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<<i))break;47 p[u][i]=p[p[u][i-1]][i-1];48 d[u][i]+=d[u][i-1]+d[p[u][i-1]][i-1];49 }50 for(i=head[u];i;i=e[i].next)51 if(!deep[e[i].to]){52 deep[e[i].to]=deep[u]+1;53 d[e[i].to][0]=e[i].w;54 p[e[i].to][0]=u;55 dfs(e[i].to);56 }57 }58 59 int main(){60 scanf("%d",&n);61 int i,u,v,res,c;62 for(i=1;i<n;i++){63 scanf("%d%d%d",&u,&v,&c);64 addedge(u,v,c);65 addedge(v,u,c);66 }67 u=1;68 for(i=0;i<n;i++)69 if(!deep[i]){70 p[i][0]=i;71 deep[i]=1;72 dfs(i);73 }74 scanf("%d",&c);75 while(c--){76 scanf("%d%d",&u,&v);77 res=lca(u,v);78 printf("%d\n",res);79 }80 return 0;81 }
无可否认，LCA的代码是有点长，但理解了还是很容易能敲出来的
小机房的树CODEVS 2370
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。