[vijos1460]拉力赛

发表于 2016-11-08   |   分类于 st , 图论  |  访问: 48 次

描述

车展结束后,游乐园决定举办一次盛大的山道拉力赛,平平和韵韵自然也要来参加大赛。

赛场上共有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。

本来是昨晚的cogs上的一场普及组t3,我一看这题之前一直没A就当复习一下倍增写了一遍

结果居然比赛完不评测,于是就不高兴安利cogs了

题目大意求树上的两个点是否第一个点为第二个点的祖先

如果是则加上他们的之间的边权值

于是我们把路上的权值用d数组保存起来

深搜跑一遍倍增造一下st表

记得用long long 类型来搞就没什么坑点了

#include <cstdio>
#include <iostream>
using namespace std;
const int _maxn=10010;
typedef long long ll;
ll fa[_maxn][20],n,m,dep[_maxn],head[_maxn],k,a[_maxn],d[_maxn][20];
bool vis[_maxn];
struct e{
	int to,dis,Next;
}edge[_maxn*200];
void add(int x,int y,int z){
	++k;
	edge[k].to=y;
	edge[k].dis=z;
	edge[k].Next=head[x];
	head[x]=k;
}
void dfs(int x){
	vis[x]=true;
	int v;
	for(int i=1;i<=16;i++){
		if((1<<i)>=dep[x])
			break;
		fa[x][i]=fa[fa[x][i-1]][i-1];
		d[x][i]=d[fa[x][i-1]][i-1]+d[x][i-1];
	}
	for(int i=head[x];i;i=edge[i].Next){
		v=edge[i].to;
		if(!vis[v]){
			d[v][0]=edge[i].dis;
			dep[v]=dep[x]+1;
			fa[v][0]=x;
			dfs(v);
		}
	}
}
ll work(int u,int v){
	int d1=dep[v]-dep[u];
	ll ans=0;
	for(int i=16;i>=0;i--){
		if(d1&(1<<i)){
			ans+=d[v][i];
			v=fa[v][i];
		}
	}
	if(v==u)
		return ans;
	return 0;
}
int main(){
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout);
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	fa[1][0]=dep[1]=1;
	dfs(1);
	ll ans=0,sum=0,temp;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(x!=y){
			if(dep[x]<dep[y]){
				if(temp=work(x,y)){
					sum+=temp;
					++ans;
				}
			}
		}
	}
	printf("%lld\n%lld\n",ans,sum);
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark