题目

描述

题目大意

给你一棵树，每次询问两个点，求出这两个点的子树的重心到其中每个点的距离和。

重心的定义是到其中每个点距离和最小的点（不一定在两棵子树内）

思考历程

想想以前我是怎么求重心的呢……先预处理出sizsizsiz，然后重心有个强大的性质：

将重心看做根节点，则其中的每课子树的大小都小于等于它的一半

然后我就乱搞出了一个方法。

可是我最终发现了一个问题：这不是传统的一棵树，这是两棵子树！

于是我的想法就崩塌了。

尝试其它想法。

设输入的两个点分别为xxx和yyy。

重心应该在xxx或yyy的子树内，或者是在xxx到yyy的路径上。

显然，如果在其它地方，一定有更优解。

首先考虑在xxx到yyy的路径上。

我们用一种思路来思考一下，假如当前在ttt点，然后通过移动到更优的位置来不断更新ttt，直到不能被更新为止。

现在t=xt=xt=x，然后ttt要向yyy移动。显然移动一段距离的贡献为sizx−sizysiz_x-siz_ysizx−sizy

然而我们发现这个是一个定值，往同一方向移动就会不停增或减。所以最终一定会移动到xxx点或yyy点。

所以没有必要考虑在xxx到yyy路径上的情况。

设all=sizx+sizyall=siz_x+siz_yall=sizx+sizy，即总大小。

考虑从uuu移到儿子vvv的贡献。

对于vvv的子树，距离都会减一，所以贡献为−sizv-siz_v−sizv

对于vvv的子树之外的地方，距离都会加一，所以贡献为all−sizvall-siz_vall−sizv

总贡献为all−2sizvall-2siz_vall−2sizv。

显然如果一直往下走，sizvsiz_vsizv递减，所以这个东西是递增的。

所以当2sizv>all2siz_v>all2sizv>all时，往下走要比现在的答案更优。

问题来了，儿子这么多，走哪边？

树链剖分，走重链！

为什么？

其实树链剖分有个性质：对于uuu的轻儿子vvv，满足2sizv<sizu2siz_v<siz_u2sizv<sizu

这个结论也是比较好证明的，vvv是轻儿子，所以它子树的大小小于等于重儿子的大小，然后就成立了。

对比一下2sizv<sizu2siz_v<siz_u2sizv<sizu和上面的式子2sizv>all2siz_v>all2sizv>all。

由于sizu<allsiz_u<allsizu<all，所以轻儿子是一定不能走下去的，只有重儿子才有可能走下去。

所以走重链就可以了。答案在xxx或yyy为开始的重链上。

有了这个结论，也可以知道重心会在更大的那棵子树中。

假设sizx>sizysiz_x>siz_ysizx>sizy，显然2sizy<all2siz_y<all2sizy<all，所以在yyy的子树中下不去！

接下来就好办了，对于每条重链，可以往下倍增，倍增到最后一个满足2sizv>all2siz_v>all2sizv>all的，沿路统计答案。

显然可以预处理出每个节点的子树中的每个点到根的路径和，设为sumsumsum。显然sumx+len∗sizy+sumysum_x+len*siz_y+sum_ysumx+len∗sizy+sumy为它的初值（len表示xxx到yyy的距离）。

然后就没有然后了。

至于一棵子树包含另一种子树的情况，就不用说了，更简单。

时间复杂度比较优秀：O((n+q)lg⁡n)O((n+q)\lg n)O((n+q)lgn)

总结

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100010

int n;

int fa[N];

struct EDGE{

	int to;

	EDGE *las;

} e[N];

int ne;

EDGE *last[N];

long long sum[N];

int dep[N],siz[N],hs[N],dfn[N],nowdfn,top[N];//hs为重儿子

long long ssiz[N];//表示从上到下的siz和

void dfs(int x){

	dfn[x]=++nowdfn;

	siz[x]=1;

	dep[x]=dep[fa[x]]+1;

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

		dfs(ei->to);

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

		siz[x]+=siz[ei->to];

		if (siz[ei->to]>siz[hs[x]])

			hs[x]=ei->to;

	}

}

void dfs2(int x,int t){

	ssiz[x]=ssiz[fa[x]]+siz[x];

	top[x]=t;

	if (hs[x])

		dfs2(hs[x],t);

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

		if (ei->to!=hs[x])

			dfs2(ei->to,ei->to);

}

int lca(int u,int v){

	while (top[u]!=top[v]){

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

			swap(u,v);

		u=fa[top[u]];

	}

	return dep[u]<dep[v]?u:v;

}

int down[N][17];//倍增数组

int main(){

	scanf("%d",&n);

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

		scanf("%d",&fa[i]);

		e[++ne]={i,last[fa[i]]};

		last[fa[i]]=e+ne;

	}

	dfs(1);

	dfs2(1,1);

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

		down[i][0]=hs[i];

	for (int i=1;i<=16;++i)

		for (int j=1;j<=n;++j)

			down[j][i]=down[down[j][i-1]][i-1];

	int T;

	scanf("%d",&T);

	while (T--){

		int x,y;

		scanf("%d%d",&x,&y);

		if (siz[x]<siz[y])

			swap(x,y);

		long long all=siz[x],ans=sum[x];

		if (!(dfn[x]<=dfn[y] && dfn[y]<dfn[x]+siz[x])){

			all+=siz[y];

			ans+=(dep[x]+dep[y]-2*dep[lca(x,y)])*siz[y]+sum[y];

		}

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

			if (all<siz[down[x][i]]*2){

				ans+=(all<<i)-2*(ssiz[down[x][i]]-ssiz[x]);

				x=down[x][i];

			}

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

	}

	return 0;

}

总结

原来树链剖分还可以这么用……

巴特西

[JZOJ4639] 【NOIP2016提高组A组7.16】Angel Beats!

题目

描述

题目大意

思考历程

总结

总结

最新文章

热门文章