比赛 |
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;
}