记录编号	127583	评测结果	AAAAAAAA
题目名称	保卫钓鱼岛!	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-10-15 21:12:41	内存使用	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};//记录i的父节点 
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];
}