点分治【bzoj1468】 Tree

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N（n<=40000）接下来n-1行边描述管道，按照题目中写的输入接下来是k

Output

一行，有多少对点之间的距离小于等于k

点分治开始入门。

点分治，主要是解决形如：给你一棵树，求树上满足XX条件的点对的对数。

所以说应对的问题很多时候都和树形DP相同。

首先告诉自己，分治是高效的算法。

想一下，平时在面对普通的分治问题，每次肯定都是半分，直到成为小问题，然后再分别解决。

为了保证点分治的高效，所以我们每一次应该将当前问题分成最平均的两个问题，放到树上就是指我们要将当前的树分成大小最平均的几棵。

那么就可以引入一个概念：树的重心。定义是在树上找一个点作为根，使得子树中的size最大者最小，这样我们就可以很好的将树平均分。

所以解决点分治问题的基本思路也就有了：

我们从整棵树开始，每一次找到当前树的重心并且以他为根，也就是将无根树转成有根树，然后对于当前的树，我们只对与当前树的根的点对进行处理。

对于这道题来说，就是找到路径经过当前根的点对，去统计这些点对中符合条件的数量对答案作出贡献。

然后对于每个子树，向下分治，继续找重心……

另外，和【bzoj3365】是一样的题。

code

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int wx=40017;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}

	return sum*f;

}

int n,m,ans,num,root,k,tmp;

int head[wx],dis[wx],size[wx];

int f[wx],vis[wx];

int temp[wx];

struct e{

	int nxt,to,dis;

}edge[wx*2];

void add(int from,int to,int dis){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	edge[num].dis=dis;

	head[from]=num;

}

void getroot(int u,int fa){

	size[u]=1;f[u]=0;

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa||vis[v])continue;

		getroot(v,u);

		size[u]+=size[v];

		f[u]=max(f[u],size[v]);

	}

	f[u]=max(f[u],tmp-size[u]);

	if(f[root]>f[u])root=u;

}

void dfs(int u,int fa){

	temp[++temp[0]]=dis[u];

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa||vis[v])continue;

		dis[v]=dis[u]+edge[i].dis;

		dfs(v,u);

	}

}

int calc(int u,int now){

	dis[u]=now;temp[0]=0;dfs(u,0);

	int l=1,r=temp[0];int re=0;

	sort(temp+1,temp+temp[0]+1);

	while(l<r){

		if(temp[r]+temp[l]<=k)re+=r-l,l++;

		else r--;

	}

	return re;

}

void slove(int u){

	vis[u]=1;ans+=calc(u,0);

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(vis[v])continue;

		ans-=calc(v,edge[i].dis);

		root=0;tmp=size[v];getroot(v,0);slove(root);

	}

}

int main(){

	n=read();

	for(int i=1;i<n;i++){

		int x,y,z;

		x=read();y=read();z=read();

		add(x,y,z);add(y,x,z);

	}

	k=read();

	f[0]=(1<<30);tmp=n;

	getroot(1,0);

	slove(root);

	printf("%d\n",ans);

	return 0;

}

巴特西

点分治【bzoj1468】 Tree

点分治【bzoj1468】 Tree

Description

Input

Output

最新文章

热门文章