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