首页 > 代码库 > ST和LCA和无根树连接
ST和LCA和无根树连接
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <string> #include<cstdio> #include<vector> #include<cmath> #include <queue> #include <map> #include <vector> #define ll __int64 #define mp make_pair<int, int> using namespace std; #define de(x) cout << #x << "=" << x << endl const int maxn=50000+10; int fa[maxn]={0}; int f[25][maxn]={0}; int len[25][maxn]={0}; int depth[maxn]={0}; vector<pair<int, int> > edge[maxn*2]; void dfs(int a) { depth[a]=depth[f[0][a]]+1; for(int i=1;(1<<i)<=depth[a];i++) { f[i][a]=f[i-1][f[i-1][a]]; len[i][a]=len[i-1][f[i-1][a]]+len[i-1][a]; } fa[a]=1; for(int i=0;i<edge[a].size();i++) { int j=edge[a][i].first; int k=edge[a][i].second; if(!fa[j]) { fa[j]=1; f[0][j]=a; len[0][j]=k; dfs(j); } } } int ST(int a,int b) { int ans=0; if(depth[a]<depth[b]) swap(a,b); for(int i=19,d=depth[a]-depth[b];i>=0;i--) { //cout<<"djfhjaksfhjkasfjk"; if(d>>i&1)//是一个&不是两个,因为这个wa了一个下午 ,ri! { //de(i); ans+=len[i][a]; a=f[i][a]; } } //cout<<a<<" "<<b<<endl; //cout<<ans<<endl; if(a==b) return ans; //cout<<ans<<endl; //s=ceil(log(dep[x])/log(2)); for(int i=19;i>=0;i--) { if(f[i][a]!=f[i][b]) { ans+=len[i][a]; a=f[i][a]; ans+=len[i][b]; b=f[i][b]; } } return ans+len[0][a]+len[0][b]; } int main() { int n,m; memset(fa,0,sizeof(fa)); memset(depth,0,sizeof(depth)); scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,len; scanf("%d %d %d",&u,&v,&len); //cout<<u<<" "<<v<<" "<<len<<endl; edge[u].push_back(mp(v,len)); //cout<<u<<" "<<v<<endl; edge[v].push_back(mp(u,len)); //cout<<u<<" "<<v<<endl; } dfs(1);//因为是无根树,所以可以任取一个节点,作为根 //for(int i=1;i<=n;i++) cout<<depth[i]<<endl; //for(int j=1;j<=n;j++) cout<<len[1][j]<<endl; /*for(int i=19;(1<<i)<=depth[j];i--) { cout<<len[i][j]<<endl; }*/ scanf("%d",&m); for(int i=0;i<m;i++) { int u,v; scanf("%d %d",&u,&v); int ans=ST(u,v); printf("%d\n",ans); } return 0; }
题目连接:http://codevs.cn/problem/2370/
ST和LCA和无根树连接
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。