题目

题目大意

给你带边权的树，然后有多高询问，每次询问距离某个点第kkk近的节点的距离。

思考

一眼看下去，首先就是想到如何动态的区间第K大，还要支持区间修改……

于是想了半天，觉得不可做……

最终在无奈之下看了题解

正解

这题需要用到点分治。

什么是点分治？

网上的解释一堆，我就随便解释一下：

对于一棵树，找出它的重心，然后分成许多棵子树，然后在这些子树中继续进行分治。

这样分治顶多有lg⁡n\lg nlgn层，所以点分治的时间复杂度是O(nlg⁡n)O(n \lg n)O(nlgn)的。

至于为什么……

我们知道一棵树的重心，它的最大子树是最小的。

所以，每一棵子树的大小不可能大于整棵树的一半（不然这个重心会调整）。

然后就是这样了……

点分治之后，就可以形成一个抽象的点分树。

每个点都会管辖一定的范围。

首先，我们可以二分一下答案，接着问题转化成和这个点的距离小于midmidmid的答案个数。

对于每个点，我们可以处理出它所管辖的范围内的所有点到它的距离，并且将这些距离排序。这样，我们计算它们的贡献时就可以二分了。

在统计答案时，首先先统计这个点对答案的贡献，然后跳到它在点分树上的父亲，再到爷爷……

不过有一点要切记，从这个点跳到父亲前，必须将这个范围的对父亲的贡献的影响减去。同样的，我们减去这个影响也利用了二分。

然后这道题就解决了。

然而不要高兴得太早，因为代码很长……（第一次打点分治打得很丑）

具体细节见程序。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#define MAXN 50000

#define MAXM 50000

int n,m;

struct EDGE{

	int to,len;

	EDGE *las;

	bool cut;//这个变量是用来辅助建立点分树的。标记过后相当于这条边被裁掉，表明两边不在同一管辖区域内

} e[MAXN*2+1];

int ne=-1;

EDGE *last[MAXN+1];

#define rev(ei) (e+(int(ei-e)^1))//表示反向边

inline void link(int u,int v,int len){

	e[++ne]={v,len,last[u],0};

	last[u]=e+ne;

}

int fat[MAXN+1],itf[MAXN+1];//fat就是father，表示点分树上的父亲；itf表示的是一个对应的东西，详见下文

int siz[MAXN+1];//子树大小，计算重心中需要用到

vector<int> dis[MAXN+1],dis2[MAXN+1];//dis表示它到管辖的范围到它的距离，dis2表示它所管辖的范围对它父亲的影响（用dis2[itf[x]]表示）

int cnt;//一个用来分配dis2的东西，详见下文

void maketree(int,int,int);//建立点分树

int ok(int,int);//ok(u,lim)//表示和u的距离小于等于lim的点数（包括u自己）

//以下是倍增LCA，根节点设为1

int dep[MAXN+1],fa[MAXN+1][17],sum[MAXN+1];//sum表示1到它的距离（用以差分计算两点间的距离）

void init_lca(int x){

	siz[x]=1;

	for (int i=1;1<<i<dep[x];++i)

		fa[x][i]=fa[fa[x][i-1]][i-1];

	for (EDGE *ei=last[x];ei;ei=ei->las)

		if (ei->to!=fa[x][0]){

			fa[ei->to][0]=x;

			sum[ei->to]=sum[x]+ei->len;

			dep[ei->to]=dep[x]+1;

			init_lca(ei->to);

			siz[x]+=siz[ei->to];//顺便将第一次的siz数组处理一下

		}

}

int lca(int u,int v){

	if (dep[u]<dep[v])

		swap(u,v);

	for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i)

		if (k&1) u=fa[u][i];

	if (u==v)

		return u;

	for (int i=15;i>=0;--i)

		if (fa[u][i]!=fa[v][i])

			u=fa[u][i],v=fa[v][i];

	return fa[u][0];

}

int main(){

	freopen("tree.in","r",stdin);

	freopen("tree.out","w",stdout);

	scanf("%d%d",&n,&m);

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

		int u,v,len;

		scanf("%d%d%d",&u,&v,&len);

		link(u,v,len),link(v,u,len);

	}

	init_lca(1);

	maketree(1,0,cnt=1);

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

		int u,k;

		scanf("%d%d",&u,&k);

		int l=1,r=500000000,res=0;

		while (l<=r){

			int mid=l+r>>1;

			if (ok(u,mid)>k)//由于包括u自己，所以是“>”

				r=(res=mid)-1;

			else

				l=mid+1;

		}

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

	}

	return 0;

}

int find_hvy(int x,int fa,int all){//找重心 （all为整棵树的大小）

	int mx=all-siz[x];//表示最大的子树

	for (EDGE *ei=last[x];ei;ei=ei->las)

		if (!ei->cut && ei->to!=fa){

			int k=find_hvy(ei->to,x,all);

			if (k)

				return k;

			mx=max(mx,siz[ei->to]);

		}

	if (mx<=all>>1)//这是重心的一个性质：最大的子树不超过总数的一半

		return x;

	return 0;

}

void get_dist(vector<int> &dis,vector<int> &dis2,int x,int fa,int di){//处理距离

	dis.push_back(di);

	dis2.push_back(di);

	siz[x]=1;

	for (EDGE *ei=last[x];ei;ei=ei->las)

		if (!ei->cut && ei->to!=fa){

			get_dist(dis,dis2,ei->to,x,di+ei->len);

			siz[x]+=siz[ei->to];//顺便将siz处理一下

		}

}

void maketree(int x,int fa,int num){

	int hvy=find_hvy(x,fa,siz[x]);//可以直接寻找重心的原因是siz早在之前就处理过了

	itf[hvy]=num;//itf表示它对应的dis2的编号

	fat[hvy]=fa;

	dis[hvy].push_back(0);

	for (EDGE *ei=last[hvy];ei;ei=ei->las)

		if (!ei->cut){

			cnt++;//新分配一个vector

			get_dist(dis[hvy],dis2[cnt],ei->to,hvy,ei->len);//处理好它自己的dis，并且处理儿子对它的影响，一举两得

			sort(dis2[cnt].begin(),dis2[cnt].end());

			rev(ei)->cut=1;

			maketree(ei->to,hvy,cnt);

		}

	sort(dis[hvy].begin(),dis[hvy].end());

}

int ok(int x,int k){

	int start=x,res=0;

	for (int lim=k;x;x=fat[x]){

		vector<int>::iterator p=upper_bound(dis[x].begin(),dis[x].end(),lim);

		res+=int(p-dis[x].begin());//记录它的贡献

		lim=k-(sum[fat[x]]+sum[start]-(sum[lca(fat[x],start)]<<1));//减去这个点父亲和起始点的距离（因为要算上起始点走到它要经过的路程）

		if (fat[x]){

			p=upper_bound(dis2[itf[x]].begin(),dis2[itf[x]].end(),lim);

			res-=int(p-dis2[itf[x]].begin());//减去它对父亲的影响

		}

	}

	return res;

}

总结

lyl说，普通的点分治，需要在父亲中减去它本身的贡献，以达到去重的目的。

巴特西

JZOJ5898【NOIP2018模拟10.6】距离统计

题目

题目大意

思考

正解

代码

总结

最新文章

热门文章