比赛 noip2016普及练习2 评测结果 AAAAAAAA
题目名称 保卫钓鱼岛! 最终得分 100
用户昵称 蜗牛哲 运行时间 0.136 s
代码语言 C++ 内存使用 0.67 MiB
提交时间 2016-11-07 20:32:27
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<string>
#include<sstream>
#include<iomanip>
using namespace std;
//=====================struct declaration======================
struct node
{
	int x,next;
	unsigned long long w;
};
//=====================var declarartion========================
const int maxn=10000+10;
node table[maxn];
int h[maxn],depth[maxn],father[maxn];
unsigned long long dis[maxn];
bool v[maxn];

int n,m,ans,len;
unsigned long long total,tot;
//=====================function declaration====================
void add1(int i,int j,unsigned long long w);
void dfs(int x);
//=====================main code===============================
int main()
{
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout);
	
	cin>>n>>m;
	for(int ii=1; ii<=n-1; ii++)
	{
		int i,j,w;
		cin>>i>>j>>w;
		add1(i,j,w);
	}
	
	v[1]=true; depth[1]=1;
	dfs(1);
	
	for(int ii=1; ii<=m; ii++)
	{
		int i,j;
		cin>>i>>j;
		if(depth[i]>=depth[j]) continue;
		
		tot=0;
		while(depth[j]>depth[i])
		{
			tot+=dis[j];
			j=father[j];
		}
		if(i!=j) continue;
		
		ans++;
		total+=tot;
	}
	
	cout<<ans<<endl;
	cout<<total<<endl;
	
	
	return 0;
}
//=====================function code===========================
void add1(int i,int j,unsigned long long w)
{
	len++;
	table[len].x=j; table[len].w=w; table[len].next=h[i];
	h[i]=len;
}
void dfs(int x)
{
	int p=h[x];
	while(p!=0)
	{
		int y=table[p].x;
		if(!v[y])
		{
			father[y]=x; dis[y]=table[p].w; depth[y]=depth[x]+1; v[y]=true;
			dfs(y);
		}
		p=table[p].next;
	}
}