Vijos——T1406 拉力赛
2024-09-06 23:36:28
https://vijos.org/p/1460
描述
车展结束后,游乐园决定举办一次盛大的山道拉力赛,平平和韵韵自然也要来参加大赛。
赛场上共有n个连通的计时点,n-1条赛道(构成了一棵树)。每个计时点的高度都不相同(父结点的高度必然大于子结点),相邻计时点间由赛道相连。由于马力不够,所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。
举办方共拟举办m个赛段的比赛,每次从第u个计时点到第v个计时点,当然其中有不少比赛韵韵的遥控车是不能参加的(因为要上坡)。平平想知道他能参加多少个赛段的比赛,并且想知道他完成这些赛段的总用时。
赛道皆为单向。
格式
输入格式
第一行两个整数n,m。
接下来n-1行每行3个整数a、b、t。
表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。
接下来m行每行2个整数u、v,意义如描述所示。
输出格式
第一行输出一个正整数,表示能参加的赛段数。
第二行输出一个正整数,表示总用时。
样例1
样例输入1
6 2
1 2 1
2 4 1
2 5 1
5 6 1
1 3 1
2 6
4 5
样例输出1
1
2
限制
各个测试点1s
提示
第一个计时点的高度是最高的;
u≠v;
对于50%的数据 n≤1000 m≤1000;
对于100%的数据 n≤10000 m≤100000;
答案小于2^64。
来源
f1zsy birdor
按标签就开始码,结果~LCA 60~
#include <algorithm>
#include <iostream>
#include <cstdio> using namespace std; #define LL long long const int N(+);
LL n,m,u,v,w; LL head[N],sumedge;
struct Edge
{
LL u,v,w,next;
Edge(LL u=,LL v=,LL next=,LL w=):
u(u),v(v),next(next),w(w){}
}edge[N];
void ins(LL u,LL v,LL w)
{
edge[++sumedge]=Edge(u,v,head[u],w);
head[u]=sumedge;
} LL dis[N],size[N],deep[N],dad[N],top[N];
void DFS(LL x)
{
size[x]=; deep[x]=deep[dad[x]]+;
for(int i=head[x];i;i=edge[i].next)
{
LL v=edge[i].v;
if(dad[x]!=v)
{
dad[v]=x;
dis[v]=dis[x]+edge[i].w,
DFS(v),size[x]+=size[v];
}
}
} void DFS_(LL x)
{
LL t=; if(!top[x]) top[x]=x;
for(int i=head[x];i;i=edge[i].next)
{
LL v=edge[i].v;
if(dad[x]!=v&&size[t]<size[v]) t=v;
}
if(t) top[t]=top[x],DFS_(t);
for(int i=head[x];i;i=edge[i].next)
{
LL v=edge[i].v;
if(dad[x]!=v&&t!=v) DFS_(v);
}
} LL LCA(LL x,LL y)
{
for(;top[x]!=top[y];x=top[dad[x]])
if(deep[top[x]]<deep[top[y]]) swap(x,y);
return deep[x]<deep[y]?x:y;
} LL ansnum,anstim; int main()
{
cin>>n>>m;
for(int i=;i<n;i++)
cin>>u>>v>>w,ins(u,v,w),ins(v,u,w);
DFS();DFS_();
for(;m;m--)
{
cin>>u>>v;
if(u==LCA(u,v))
ansnum++,anstim+=dis[v]-dis[u];
}
cout<<ansnum<<endl<<anstim;
return ;
}
AWWAWAAAWA
然后看题解,用sta记录点的先序遍历,ove记录后序遍历,
如果sta[u]<sta[v]&&ove[u]>ove[v]就说明u是v的祖先~
#include <iostream>
#include <cstdio> using namespace std; const int M(+);
int n,m,u,v,ansnum;
long long w,anstim; int head[M],sumedge;
struct Edge
{
int u,v,next,dis;
long long w;
Edge(int u=,int v=,int next=,int dis=):
u(u),v(v),next(next),dis(dis){}
}edge[M];
void ins(int u,int v,int w)
{
edge[++sumedge]=Edge(u,v,head[u],w);
head[u]=sumedge;
} int dis[M],sta[M],ove[M],tim;
void DFS(int now,int val)
{
sta[now]=++tim; dis[now]=val;
for(int i=head[now];i;i=edge[i].next)
DFS(edge[i].v,val+edge[i].dis);
ove[now]=++tim;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%d%d%I64d",&u,&v,&w),ins(u,v,w);
DFS(,);
for(;m;m--)
{
scanf("%d%d",&u,&v);
if(sta[u]<sta[v]&&ove[u]>ove[v])
ansnum++,anstim+=dis[v]-dis[u];
}
cout<<ansnum<<endl<<anstim;
return ;
}
最新文章
- liunx之:解决liunx下dns配置重启失效的问题
- Android开发学习之路-使用AsyncTask进行异步操作
- RMAN备份注意事项
- OS开发拓展篇—应用之间的跳转和数据传
- 有联系的jQuery选择器
- 项目结队开发---NABC分析(成员)
- MyEclipse 简单快捷键
- POJ 1922 Ride to School(贪心+模拟)
- 【转】shell 教程——05 第一个Shell脚本
- SQL Server 2008 常见异常收集(持续更新)
- ubuntu12 下怎样上网
- mac和windows系统下 eclipse svn 设置代理服务器
- List Set Map用法和区别
- 创建zend framework 项目要注意的
- NDK 开发(Android.mk配置)
- Beta 第四天
- Luogu P2602 [ZJOI2010]数字计数
- 第三个sprint冲刺第一阶段
- ceph API之PHP的S3-SDK包的泛域名解析问题
- 利用angularjs完成注册表单
热门文章
- 一入python深似海--python之道
- QUERY_REWRITE_ENABLED
- UVa 10954 Add All 贪心
- cocos2d-x3.0 关于CCAnimate 的一些资料
- 4. idea常用快捷键设置(改为eclipse相似)
- IE11 mobile 的 UA(User-Agent)
- PostgreSQL Replication之第四章 设置异步复制(2)
- RMAN备份脚本--DataGuard primary
- JDOJ 2939: Suffix Automaton 广义后缀自动机_统计子串
- nginx配置虚拟域名