记录编号	127566	评测结果	AAAAAAAA
题目名称	保卫钓鱼岛!	最终得分	100
用户昵称	MINE·MINE	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-10-15 20:55:31	内存使用	0.57 MiB

#include<cstdio>
#include<queue>
using namespace std;
#define Size 10001
int n,m;
struct Line
{
	int next;
	int to;
	int data;
}net[Size]={0};
int head[Size]={0};
int root=0;
int father[Size]={0};
void dispose(int,int,int);
void find(int);
void search(int);
int degree[Size]={0};
long long tot=0,ans=0;
int dis[Size]={0};
int main()
{
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout);
	scanf("%d%d",&n,&m);
	int start,end,i,j,data;	
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&start,&end,&data);
		dispose(start,end,data);
		father[end]=start;
	}
	find(1);
	search(root);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&start,&end);
		if(degree[start]<degree[end])
		{
			tot++;
			ans+=dis[end]-dis[start];
		}
	}
	printf("%lld\n%lld",tot,ans);
	return 0;
}
void find(int x)
{
	if(!father[x])
	{
		root=x;
		return ;
	}
	else
	find(father[x]);
}
void search(int x)
{
	queue<int> q;
	degree[x]=1;
	q.push(x);
	while(!q.empty())
	{
		int k=q.front();
		for(int i=head[k];i!=0;i=net[i].next)
		{
			int t=net[i].to;
			degree[t]=degree[k]+1;
			dis[t]=dis[k]+net[i].data;
			q.push(t);
		}
		q.pop();
	}
}
void dispose(int x,int y,int z)
{
	head[0]++;
	net[head[0]].data=z;
	net[head[0]].next=head[x];
	net[head[0]].to=y;
	head[x]=head[0];
}