codevs 2370 小机房的树 （LCA）

codevs 2370 小机房的树 （LCA）

Description

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

Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。(1<=n<=50000， 1<=m<=75000， 0<=c<=1000)第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

Output Description

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

Sample Input

31 0 12 0 131 02 01 2

Sample Output

112

思路

LCA 问题，我们为每个点设置一个权值 ​​tim[i]​​​ 等于从根节点到其路径中所有边权的和，于是虫子所要爬行的最短路径权值为 ​​tim[u]+tim[v]-2*tim[lca(u,v)]​​ 。

采用离线 tarjan 算法可以解决这一问题，每条边的权值我们可以将其保存在子节点中。

不过缺点就是离线算法不能保证计算顺序与输入顺序的一致，因此我们采用一个变量来标记每个查询的序号，得出所有结果后根据该序号排序后输出。

AC 代码

#include#include#include#include#includeusing namespace std;typedef pair P;const int maxn=51000;int fa[maxn];int rk[maxn];bool visit[maxn];int tim[maxn]; //将 u->v 路径权值存储在 v 中vector tree[maxn];vector

Qes[maxn];vector

ans;int ancestor[maxn];struct node{ int to; int next; int cost;} edge[maxn<<1];int head[maxn<<1],tot;void addedge(int u,int v,int cost){ edge[tot].to=v; edge[tot].next=head[u]; edge[tot].cost=cost; head[u]=tot++;}void init(int n){ memset(rk,0,sizeof(rk)); memset(visit,false,sizeof(visit)); memset(ancestor,0,sizeof(ancestor)); memset(tim,0,sizeof(tim)); memset(head,-1,sizeof(head)); tot=0; ans.clear(); for(int i=0; irk[y]) fa[y]=x; else { fa[x]=y; if(rk[x]==rk[y]) rk[y]++; }}void LCA(int u,int pa,int cost){ ancestor[u]=u; tim[u]+=cost+tim[pa]; // u 点权值 = 父节点权值 + 边权值 for(int i=head[u]; i!=-1; i=edge[i].next) { int to=edge[i].to; if(to==pa)continue; LCA(to,u,edge[i].cost); union_set(u,to); ancestor[find_set(u)]=u; } visit[u]=true; int len = Qes[u].size(); for(int i=0; i>n) { init(n); for(int i=1; i>u>>v>>cost; addedge(u,v,cost); addedge(v,u,cost); } cin>>m; for(int i=0; i>u>>v; Qes[u].push_back(P(i,v)); //其中 i 标记其输入的序号 Qes[v].push_back(P(i,u)); } LCA(0,-1,0); sort(ans.begin(),ans.end()); //因为 tarjan 离线算法不能保证计算和输入顺序一致 int len=ans.size(); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。