时间戳

首页 > 技术文章 > [HNOI2014]世界树

[HNOI2014]世界树

Troverld 2021-04-06 13:30 原文

IV.[HNOI2014]世界树

人傻常数大没错了，\(n\log n\)还会TLE

首先当然是建出虚树来。

然后，对于虚树中每个节点（不管是否是实点），我们可以DP出管辖它的那个节点，设为\(f_x\)。这个可以通过二次扫描与换根法在\(O(k)\)的时间内通过两次dfs求出，假如你使用ST表求LCA的话。这里我使用了倍增，因此复杂度为\(O(k\log n)\)。

我们设\(g_x\)表示\(x\)节点（必须是个实点）管辖了多少节点，即询问的答案。

首先，我们先求出不在虚树中的子树的贡献。设\(sz_x\)为原树中\(x\)节点的子树大小。则对于虚树中每个点\(x\)，\(sz_x-\sum\limits_{y\in son_x}sz_y\)即是不在虚树中子树的贡献（\(x\)自身也包含在内）。这个可以通过一次dfs求出。

但是，这个\(sz_y\)可不能直接用\(y\)的\(sz\)——它应该是原树上\(x\)在\(y\)方向的那个儿子（设为\(Q\)）的\(sz\)。这个可以通过倍增求出，当然如果你不嫌麻烦，可以通过长链剖分来在\(O(1)\)时间内求出树上\(k\)级祖先。因为前面LCA我就使用了倍增，这里仍然使用倍增。

然后就是虚树上路径的贡献了。对于虚树上一条边\((x,y)\)且\(x\)是\(y\)的父亲，如果\(f_x=f_y\)，则整条边都归\(f_x\)管辖，贡献是\(sz_Q-sz_y\)，其中\(Q\)是\(x\)在\(y\)方向的儿子。

否则，即\(f_x\neq f_y\)，我们可以直接找出从\(y\)点往上有\(P\)个节点是归\(f_y\)管辖的。则一共有\(sz_P-sz_y\)个节点归\(y\)管理，\(sz_Q-sz_P\)个节点归\(x\)管理。

注意到这里的\(sz_Q\)在子树贡献和路径贡献中被算了两次，一次加一次减。故两次可以直接抵消。

复杂度\(O(n\log n)\)（就算你丧心病狂用了ST表和长链剖分，复杂度瓶颈的sort你仍无法解决）

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,m,anc[300100][20],dfn[300100],tot,dep[300100],sz[300100];
namespace real{
	vector<int>v[300100];
	void dfs(int x,int fa){
		anc[x][0]=fa,dep[x]=dep[fa]+1,dfn[x]=++tot,sz[x]=1;
		for(auto y:v[x])if(y!=fa)dfs(y,x),sz[x]+=sz[y];
	}	
}
int MIN(int x,int y){
	return dep[x]<dep[y]?x:y;
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=anc[x][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}
int DIS(int x,int y){
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
int ANC(int x,int z){
	for(int i=19;i>=0;i--)if((1<<i)<=z)x=anc[x][i],z-=(1<<i);
	return x;
}
namespace imag{
	int stk[300100],tp,res,a[300100],r[300100],f[300100],g[300100];
	bool mark[300100];
	vector<int>v[300100];
	bool cmp(int x,int y){
		return dfn[x]<dfn[y];
	}
	void ins(int x){
		mark[x]=true;
		if(!tp){stk[++tp]=x;return;}
		int lca=LCA(x,stk[tp]);
		while(tp>=2&&dep[lca]<dep[stk[tp-1]])v[stk[tp-1]].push_back(stk[tp]),tp--;
		if(tp&&dep[lca]<dep[stk[tp]])v[lca].push_back(stk[tp--]);
		if(!tp||stk[tp]!=lca)stk[++tp]=lca;
		stk[++tp]=x;
	}
	void fin(){
		while(tp>=2)v[stk[tp-1]].push_back(stk[tp]),tp--;
		tp--;
	}
	void dfs1(int x){
		if(mark[x])f[x]=x;
		else f[x]=0;
		for(auto y:v[x]){
			dfs1(y);
			if(!f[y])continue;
			if(!f[x])f[x]=f[y];
			else{
				int X=DIS(x,f[x]),Y=DIS(x,f[y]);
				if(X>Y)f[x]=f[y];
				if(X==Y&&f[x]>f[y])f[x]=f[y];
			}
		}
	}
	void dfs2(int x){
		for(auto y:v[x]){
			if(!f[x])continue;
			if(!f[y])f[y]=f[x];
			else{
				int X=DIS(y,f[x]),Y=DIS(y,f[y]);
				if(X<Y)f[y]=f[x];
				if(X==Y&&f[x]<f[y])f[y]=f[x];
			}
			dfs2(y);
		}
	}
	void dfs3(int x){
		g[f[x]]+=sz[x];
		for(auto y:v[x])dfs3(y);
	}
	void dfs4(int x){
		for(auto y:v[x]){
			dfs4(y);
			if(f[x]==f[y])g[f[x]]-=sz[y];
			else{
				int X=DIS(x,f[x]),Y=DIS(y,f[y]),Z=dep[y]-dep[x]-1,P=0;
				int D=min(abs(X-Y),Z);
				if(Y<X)P+=D;
				Z-=D;
				P+=(Z+(f[y]<f[x]))/2;
				P=ANC(y,P);
//				printf("(%d,%d):%d\n",x,y,P);
				g[f[y]]+=sz[P]-sz[y];
				g[f[x]]-=sz[P];
			}
		}
	}
	void dfs5(int x){
		g[x]=mark[x]=0;
		for(auto y:v[x])dfs5(y);
		v[x].clear();
	}
	void work(){
		int q;
		res=0,scanf("%d",&q);
		for(int i=1;i<=q;i++)scanf("%d",&a[i]),r[i]=a[i];
		sort(a+1,a+q+1,cmp);
		if(a[1]!=1)stk[++tp]=1;
		for(int i=1;i<=q;i++)ins(a[i]); 
		fin();
		dfs1(1);
		dfs2(1);
		dfs3(1);
//		for(int i=1;i<=q;i++)printf("%d ",g[r[i]]);puts("");
		dfs4(1);
		for(int i=1;i<=q;i++)printf("%d ",g[r[i]]);puts("");
		dfs5(1);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),real::v[x].push_back(y),real::v[y].push_back(x);
	real::dfs(1,0);
	for(int j=1;j<20;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];
	scanf("%d",&m);
	while(m--)imag::work();
	return 0;
}

推荐阅读