比赛 noip2016普及练习2 评测结果 AAAAAAAA
题目名称 保卫钓鱼岛! 最终得分 100
用户昵称 liuliuliu 运行时间 0.111 s
代码语言 C++ 内存使用 2.99 MiB
提交时间 2016-11-07 20:38:26
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <sstream>
#include <queue>
#include <set> 
#include <map> 
using  namespace std;
 
const int maxn=10000+10;
const int maxm=1000+10;

struct node
{
	unsigned long long x,next;
	unsigned long long w;
};
node table[100000+10];
unsigned long long ind[maxn],h[maxn];
unsigned long long n,m,ans,cnt1,cnt2;
bool used[maxn];
unsigned long long father[maxn],depth[maxn],dis[maxn];
unsigned long long len;
unsigned long long a,b,c;
unsigned long long getint()
{
	unsigned long long x=0,s=1;
	char ch=' ';
	while (ch<'0' || ch>'9')
	{
		ch=getchar();
		if (ch=='-') s=-1;
	}
		
	while (ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*s;
}
void add1(unsigned long long i, unsigned long long 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)
{
	unsigned long long p=h[x];
	while (p)
	{
		int u=table[p].x;
		if (!used[u])
		{
			father[u]=x; used[u]=true; depth[u]=depth[x]+1;
			dis[u]=table[p].w;
			
			dfs(u);
		}
		p=table[p].next;
	}
}
int main()
{
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout); 
	n=getint();m=getint();
	for(int k=1;k<n;k++)
	{
		a=getint();b=getint();c=getint();
		//scanf("%d%d%d",&i,&j,&w);
		add1(a,b,c);
		ind[b]++;
	}
	unsigned long long start;
	for(int i=1;i<=n;i++)
	{
		if(ind[i]==0)
		{
			start=i;
			break;
		}
	}
	used[start]=true; depth[start]=1;
	dfs(start);
	for (int k=1; k<=m; k++)
	{
		int i,j;
		ans=0;
		bool flag=false;
		scanf("%d%d",&i,&j);
		
		if (depth[i]>=depth[j]) 
		{
			continue;
		}
		while(i!=j)
		{
			ans+=dis[j];
			j=father[j];
			if(depth[i]>depth[j])
			{
				flag=true;
				break;
			}
		}
		if(!flag)
		{
			cnt1++;
			cnt2+=ans;
		}
	}
	cout<<cnt1<<endl<<cnt2<<endl;
	return 0;
}