比赛 noip2016普及练习2 评测结果
题目名称 保卫钓鱼岛! 最终得分 0
用户昵称 JVendetta 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-11-07 21:17:12
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define N 100010
using namespace std;

ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll ans,ansn,len[2],head[2][N],dist[N],f[N],vis[N];
struct edge{
	ll to,dis,go;
}road[2][N<<1];
void add(int x,ll a,ll b,ll c){
	len[x]++;
	road[x][len[x]].to=b;
	road[x][len[x]].dis=c;
	road[x][len[x]].go=head[x][a];
	head[x][a]=len[x];
	return ;
}
ll find(ll x){return f[x]==x?x:f[x]=find(f[x]);}
void marge(ll x,ll y){
	x=find(x),y=find(y);
	if(x!=y)
		f[y]=x;
	return ;
}
void Tarjan(ll u,ll dev){
	ll i=head[0][u],v;
	while(i!=-1){
		v=road[0][i].to;
		if(vis[v]) continue;
		Tarjan(v,dev+road[0][i].dis);
		marge(u,v);
		vis[v]=1;
		i=road[0][i].go;
	}
	dist[u]=dev;
	i=head[1][u];
	while(i!=-1){
		v=road[1][i].to;
		if(u==v) continue;
		if(vis[v]){
			ll x=find(u),y=find(v);
			if(x==y)
				ansn++,ans+=dist[u]+dist[v]-2*dist[x];
		} 
		i=road[1][i].go;
	}
	return ;
}
int main(){
	freopen("diaoyu.in","r",stdin);
	freopen("diaoyu.out","w",stdout);
	memset(head,-1,sizeof(head)); 
	ll n,m,i,a,b,c;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<n;i++){
		scanf("%lld%lld%lld",&a,&b,&c);
		add(0,a,b,c);
	}
	for(i=1;i<=n;i++) f[i]=i;
	for(i=1;i<=m;i++){
		scanf("%lld%lld",&a,&b);
		add(1,a,b,c),add(1,b,a,0);
	}
	Tarjan(1,0); 
	printf("%lld\n%lld\n",ansn,ans);
	return 0;
}