比赛 noip2016普及练习2 评测结果 AAAAAAAA
题目名称 保卫钓鱼岛! 最终得分 100
用户昵称 明天 运行时间 0.063 s
代码语言 C++ 内存使用 1.24 MiB
提交时间 2016-11-07 20:28:45
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct node
{
	int x,next;
};

const int maxn=10000+1;
const int maxm=100000+1;

int n,m;
int h[maxn],len;
node table[maxm];

int x,y,z;
bool used[maxn];
int w[maxn],depth[maxn],father[maxn];
int ans;
long long total;

void dfs(int x);
inline int getint()
{
	int x=0;
	char ch=getchar();
	while (ch<'0' || ch>'9')
		ch=getchar();
	while (ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
inline void add1(int i, int j)
{
	len++;
	table[len].x=j; table[len].next=h[i];
	h[i]=len;
}
int main()
{
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (int k=1; k<n; k++)
	{
		x=getint(); y=getint(); z=getint();
		add1(x,y);
		
		w[y]=z; father[y]=x;
	}
	
	dfs(1);
	
	for (int k=1; k<=m; k++)
	{
		x=getint(); y=getint();
		
		if (x==y) continue;
		int t=0;;
		while (depth[y]>depth[x])
		{
			t+=w[y];
			y=father[y];
		}
		if (x==y)
		{
			total+=t; ans++;
		}
	}
	
	cout<<ans<<endl;
	cout<<total<<endl;
	
	return 0;
}

void dfs(int x)
{
	int p=h[x];
	while (p)
	{
		int u=table[p].x;
		if (!used[u])
		{
			used[u]=true; depth[u]=depth[x]+1;
			dfs(u);
		}
		p=table[p].next;
	}
}