比赛 |
noip2016普及练习2 |
评测结果 |
|
题目名称 |
保卫钓鱼岛! |
最终得分 |
0 |
用户昵称 |
Steve |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2016-11-07 21:13:20 |
显示代码纯文本
#include <cstdio>
#include <iostream>
using namespace std;
const int _maxn=10010;
typedef long long ll;
ll fa[_maxn][20],n,m,dep[_maxn],head[_maxn],k,a[_maxn],d[_maxn][20];
bool vis[_maxn];
struct e{
int to,dis,Next;
}edge[_maxn*200];
void add(int x,int y,int z){
++k;
edge[k].to=y;
edge[k].dis=z;
edge[k].Next=head[x];
head[x]=k;
}
void dfs(int x){
vis[x]=true;
int v;
for(int i=1;i<=16;i++){
if((1<<i)>=dep[x])
break;
fa[x][i]=fa[fa[x][i-1]][i-1];
d[x][i]=d[fa[x][i-1]][i-1]+d[x][i-1];
}
for(int i=head[x];i;i=edge[i].Next){
v=edge[i].to;
if(!vis[v]){
d[v][0]=edge[i].dis;
dep[v]=dep[x]+1;
fa[v][0]=x;
dfs(v);
}
}
}
ll work(int u,int v){
int d1=dep[v]-dep[u];
ll ans=0;
for(int i=16;i>=0;i--){
if(d1&(1<<i)){
ans+=d[v][i];
v=fa[v][i];
}
}
if(v==u)
return ans;
return 0;
}
int main(){
freopen("diaoyu.in","r",stdin);
freopen("diaoyu.out","w",stdout);
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
fa[1][0]=dep[1]=1;
dfs(1);
ll ans=0,sum=0,temp;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if(x!=y){
if(dep[x]<dep[y]){
if(temp=work(x,y)){
sum+=temp;
++ans;
}
}
}
}
printf("%lld\n%lld\n",ans,sum);
return 0;
}