输出有个坑,两个月之前就没对,,今天又被坑了一次

求联通树上三个点的路径长度,只要求两两点对的最短路径,加起来除以二即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define maxn 50005
#define DEG 20
struct Edge{
int to,next,w;
}edge[maxn*];
int head[maxn],tot;
inline void addedge(int u,int v,int w){
edge[tot].to=v;
edge[tot].next=head[u];
edge[tot].w=w;
head[u]=tot++;
}
int deg[maxn],depth[maxn],fa[maxn][DEG];
int flag[maxn];
void bfs(int root){
queue<int> que;
deg[root]=depth[root]=;
fa[root][]=root;
que.push(root);
while(!que.empty()){
int tmp=que.front();que.pop();
for(int i=;i<DEG;i++)
fa[tmp][i]=fa[fa[tmp][i-]][i-];
for(int i=head[tmp];i!=-;i=edge[i].next){
int v=edge[i].to;
if(v==fa[tmp][]) continue;
deg[v]=deg[tmp]+;depth[v]=depth[tmp]+edge[i].w;
fa[v][]=tmp;
que.push(v);
}
}
}
int query(int u,int v){
if(deg[u]>deg[v]) swap(u,v);
int hu=deg[u],hv=deg[v],tu=u,tv=v;
for(int det=hv-hu,i=;det;det>>=,i++)
if(det&) tv=fa[tv][i];
if(tu==tv) return tu;
for(int i=DEG-;i>=;i--){
if(fa[tu][i]==fa[tv][i])continue;
tu=fa[tu][i];tv=fa[tv][i];
}
return fa[tu][];
}
void init(){
tot=;
memset(head,-,sizeof head);
memset(depth,,sizeof depth);
memset(deg,,sizeof deg);
}
int main(){
int n,q,u,v,w;
int flagg=;
while(~scanf("%d",&n)){
init();
for(int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);addedge(v,u,w);
flag[v]=;
}
int root;
for(int i=;i<n;i++) if(!flag[i]){root=i;break;}
bfs(root); if(flagg) putchar('\n');
else flagg=;
scanf("%d",&q);
int a,b,c;
while(q--){
scanf("%d%d%d",&a,&b,&c);
int tmp1=query(a,b);
int dis1=depth[a]+depth[b]-depth[tmp1]*; int tmp2=query(b,c);
int dis2=depth[b]+depth[c]-depth[tmp2]*; int tmp3=query(a,c);
int dis3=depth[a]+depth[c]-depth[tmp3]*;
printf("%d\n",(dis1+dis2+dis3)/);
}
}
}

最新文章

  1. iOS中 HTTP/Socket/TCP/IP通信协议详解
  2. 2.servlet的会话机制session
  3. pip/matplot/pandas的安装和使用
  4. GridView点击排序
  5. springAOP配置文件
  6. hdu 4859 海岸线 最小割
  7. php-fpm配置文件详解
  8. c++ 异常处理 assert | try
  9. linux压缩与解压缩 tar命令
  10. c#秒转时分秒
  11. QTP小应用一则
  12. Let&#39;sencrypt认证的网站Https配置
  13. 迭代子模式(Iterator)
  14. jquery checkbox勾选/取消勾选checked属性不生效问题
  15. Linux基础知识第七讲,用户权限以及用户操作命令
  16. 转:UML工具Astah的使用
  17. 10: VMware中扩展根分区
  18. 【原创】&lt;Debug&gt; “duplicate connection name”
  19. yum安装jdk如何配置JAVA_HOME
  20. Linux常见问题总结【转】

热门文章

  1. vue props的理解
  2. servlet dispatcher .forward(request, response); 进入其它servlet【原】
  3. oracle解除锁表【原】
  4. UESTC - 1324 卿学姐与公主
  5. Neural Networks and Deep Learning(week3)Planar data classification with one hidden layer(基于单隐藏层神经网络的平面数据分类)
  6. storm-starter 例子学习
  7. C#复杂类型序列化
  8. MySQL - 日常操作三 mysql慢查询;
  9. luogu P2900 [USACO08MAR]土地征用Land Acquisition
  10. 2018-2019-2 网络对抗技术 20165320 Exp2 后门原理与实践