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