codevs2370 小机房的树 x
2024-08-30 19:01:58
2370 小机房的树
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
小机房有棵焕狗种的树,树上有N个节点,节点标号为0到N-1,有两只虫子名叫飘狗和大吉狗,分居在两个不同的节点上。有一天,他们想爬到一个节点上去搞基,但是作为两只虫子,他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量(从父亲节点爬到此节点也相同),他们想找出一条花费精力最短的路,以使得搞基的时候精力旺盛,他们找到你要你设计一个程序来找到这条路,要求你告诉他们最少需要花费多少精力
输入描述 Input Description
第一行一个n,接下来n-1行每一行有三个整数u,v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ,v 表示两只虫子所在的节点
输出描述 Output Description
一共有m行,每一行一个整数,表示对于该次询问所得出的最短距离。
样例输入 Sample Input
3
1 0 1
2 0 1
3
1 0
2 0
1 2
样例输出 Sample Output
1
1
2
数据范围及提示 Data Size & Hint
1<=n<=50000, 1<=m<=75000, 0<=c<=1000
思路:
裸的求LCA的题
坑点:
记住输入的时候是从0开始编的号!!!
上代码:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int N = ;
const int M = ;
int top=,cnt=,dad[N],ans[N],dis[N],lca[M];
bool used[N]; struct heads {
int head;
}v1[N],v2[N]; struct edge {
int v,next,w;
}e1[N<<]; struct qedge {
int u,v,next;
}e2[M<<]; void chu()
{
memset(v1,-,sizeof(v1));
memset(v2,-,sizeof(v2));
memset(used,,sizeof(used));
} void add1(int u,int v,int w)
{
e1[++top].w=w;
e1[top].v=v;
e1[top].next=v1[u].head;
v1[u].head=top;
} void add2(int u,int v)
{
e2[++cnt].u=u;
e2[cnt].v=v;
e2[cnt].next=v2[u].head;
v2[u].head=cnt;
} int getdad(int x)
{return dad[x] = x == dad[x] ? x : getdad(dad[x]);} int getdis(int i)
{return dis[e2[i<<].u]+dis[e2[i<<].v]-(dis[lca[i]]<<);} void Tarjan(int u)
{
dad[u]=u;
used[u]=true;
for(int i=v1[u].head;i!=-;i=e1[i].next)
{
int v=e1[i].v;
if(used[v])
continue;
dis[v]=dis[u]+e1[i].w;
Tarjan(v);
dad[v]=u;
}
int Ms;
for(int i=v2[u].head;i!=-;i=e2[i].next)
{
int v = e2[i].u == u ? e2[i].v : e2[i].u;
if(used[v])
lca[i>>]=getdad(dad[v]);
}
} int main()
{
int n,m,u,v,w;
scanf("%d",&n);
chu();
--n;
while(n--)
{
scanf("%d%d%d",&u,&v,&w);
++u,++v;///从0开始编号的
add1(u,v,w),add1(v,u,w);
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
++u,++v;
add2(u,v),add2(v,u);
}
Tarjan();
for(int i=;i<=m;i++)
printf("%d\n",getdis(i));
return ;
}
最新文章
- CSS基础篇之背景、过渡动画
- imx6 关闭调试串口
- Centos5下安装监控工具nmon
- hduoj 4706 Herding 2013 ACM/ICPC Asia Regional Online —— Warmup
- Expect:100-continue
- spark概论,补充
- Makefile之wildcard
- 【DOM】2.闭包
- docker学习笔记11:Dockerfile 指令 CMD介绍
- hdu 神、上帝以及老天爷
- python爬虫提取冰与火之歌五季的种子
- pyspider和pyquery总结
- javascript xml字符串转为json对象
- SOAP UI-----测webservice接口
- vue2.0项目实战(4)生命周期和钩子函数详解
- (常用)time,datetime,random,shutil(zipfile,tarfile),sys模块
- 【iCore4 双核心板_ARM】例程十八:USBD_VCP实验——虚拟串口
- QWebView崩溃的问题
- Monkey学习网址
- js正则表达使用实例