3
28
2016
1

[POJ1741] Tree

点分治第一题

这题我们考虑点分治

首先我们需要找到树的重心

然后做一遍

然后分成左右两块继续做,每一块重复上面的操作

具体的,我们每次计算每个点到重心的距离

然后放到一个数组里,再将距离和小于k的算进去

但是有可能重复统计了子树里面的数值

所以点分治的时候再减一下就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,k,h[10005],en,mx[10005],siz[10005],ans,root,val,vis[10005],temp[10005],cnt;

struct Edge{
int b,v,next;
}e[20005];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa && !vis[v]){
		DfsSiz(v,u);
		siz[u]+=siz[v];
		mx[u]=max(mx[u],siz[v]);
	}
}
}

void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}

void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}

int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
int i=1,j=cnt;
while(i<j){
	while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
return now;
}

void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
	int v=e[i].b;
	if(!vis[v]){
		ans-=Cal(v,e[i].v);
		Dfs(v);
	}
}
}

int main(){
freopen("1741.in","r",stdin);
freopen("1741.out","w",stdout);
while(scanf("%d %d",&n,&k),n|k){
	memset(h,0,sizeof(h));
	memset(vis,0,sizeof(vis));
	ans=en=0;
	for(int i=1;i<n;i++){
		int sa,sb,sc;
		scanf("%d %d %d",&sa,&sb,&sc);
		AddEdge(sa,sb,sc);
		AddEdge(sb,sa,sc);
	}
	Dfs(1);
    printf("%d\n",ans);
}
return 0;
}
Category: 其他OJ | Tags: OI poj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com