首页 > 代码库 > 【HDU 2586】LCA模板
【HDU 2586】LCA模板
在一棵树上 求2个点的最短距离。那么首先利用LCA找到2个点的近期公共祖先
公式:ans = dis(x) + dis(y) - 2 * dis(lca(x,y))
这里的dis(x)指的上x距离根节点的距离
注意一些细节方面,比方数组的越界问题:
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int maxn = 45555; struct Edge{ int to; LL dist; Edge(int to,LL dist):to(to),dist(dist){}; }; int n,m; int deep[maxn],pa[maxn][22]; LL dis[maxn]; vector<Edge>G[maxn]; void init(){ memset(pa,-1,sizeof(pa)); for(int i = 1; i <= n; i++) G[i].clear(); } //----------------LAC--------------------------- void dfs(int pos,int d,LL dist){ //printf("[%d %d]\n",pos,dist); deep[pos] = d; dis[pos] = dist; int Size = G[pos].size(); for(int i = 0; i < Size; i++) dfs(G[pos][i].to,d + 1,dist + G[pos][i].dist); } void lca_init(){ for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i <= n; i++) if(pa[i][j - 1] != -1) pa[i][j] = pa[pa[i][j - 1]][j - 1]; } int lca(int a,int b){ if(a == b) return a; if(deep[a] < deep[b]) swap(a,b); int i; for(i = 0;(1 << i) <= deep[a]; i++); for(int j = i; j >= 0; j--) if(pa[a][j] != -1 && deep[pa[a][j]] >= deep[b]) a = pa[a][j]; if(a == b) return b; for(int j = i; j >= 0; j--) if(pa[a][j] != -1 && deep[pa[a][j]] != deep[pa[b][j]]){ a = pa[a][j]; b = pa[b][j]; } return pa[a][0]; } //------------------------------------------------- int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); int x,y,z; init(); for(int i = 0; i < n - 1; i++){ scanf("%d%d%d",&x,&y,&z); G[x].push_back(Edge(y,z)); pa[y][0] = x; } for(int i = 1; i <= n; i++)if(pa[i][0] == -1){ dfs(i,0,0); break; } lca_init(); for(int i = 0; i < m; i++){ scanf("%d%d",&x,&y); LL ans = dis[x] + dis[y] - 2 * dis[lca(x,y)]; printf("%I64d\n",ans); } } return 0; }
【HDU 2586】LCA模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。