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