比赛 noip2016普及练习2 评测结果
题目名称 保卫钓鱼岛! 最终得分 0
用户昵称 God-Nan 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-11-07 21:09:48
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
void addpoint(int f,int t,int p);
void cool(int f);
int n,m;
bool flag[22000];
long long ans1,ans2,dis[11000];
int head[22000],power[22000],to[22000],next[22000],star;
int time1[11000],time2[11000],time;
int main()
{
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout);
	int i,p,k,l,f,t;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	head[i]=-1;
	for(i=1;i<=n-1;i++)
	{
		scanf("%d%d%d",&f,&t,&p);
		addpoint(f,t,p);
		addpoint(t,f,p);
	}
	
	cool(1);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&f,&t);
		if(time1[f]<=time1[t]&&time2[f]>=time2[t])
		ans1++,ans2+=dis[t]-dis[f];
	}
	printf("%lld\n%lld",ans1,ans2);
	
	return 0;
}
void addpoint(int f,int t,int p)
{
    next[++star]=head[f];
	head[f]=star;
	to[star]=t;
	power[star]=p;
	return ;	
}
void cool(int f)
{
	flag[f]=1;
	time1[f]=++time;
    int p;	
    p=head[f];
    while(p!=-1)
    {
    	if(!flag[to[p]])
    	{
    	dis[to[p]]=dis[f]+power[p];
    	cool(to[p]);
        }
    	p=next[p];
    }
    
    time2[f]=++time;
    return ;
}