「HNOI2014」世界树 - 虚树+树形动规+倍增

题目大意

    给你一个$n$个节点的树，现在有$q$组询问，对于第$i$组询问先给你一个$M_i$个树中的节点，设这些节点为关键点，对于树中的每个点都属于它最近的关键点，如有多个则选编号最小的那个。要求找出每个关键点包含了多少个树中的节点（包括自己）。
$\quad \quad n\le300000,q\le300000,\sum M\le300000$

---

题目分析

发现范围中存在对点集总和的限制，考虑建立虚树。

加入建立好的虚树中都是关键点，那么我们对虚树上的虚边进行一下划分即可得出答案。
但是虚树上除了关键点还有他们的$lca$，故我们需要转化。

不妨用两次树形动规求出每个虚树上的非关键点被哪个关键点所覆盖，那么我们通过枚举虚树上的虚边$(u\rightarrow v)$，那么我们可以倍增划分出$Belong[u],Belong[v]$的分界线，问题完美解决。

若计算上求$lca$的时间复杂度，则总时间是$O(\sum M\log^2\sum M)$的。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=300005;

int n,q,step,First[maxn],Last[maxn],Belong[maxn],Depth[maxn],Size[maxn],Remain[maxn],p[maxn][25],b[maxn],c[maxn],Ans[maxn];
vector<int>edges[maxn],tree[maxn],a;

bool cmp(int a,int b) {
	return First[a]<First[b];
}

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void AddEdge2(int x,int y) {
	tree[x].push_back(y);
}

void Dfs(int Now,int fa,int depth) {
	First[Now]=++step;
	Depth[Now]=depth;
	Size[Now]=1;
	p[Now][0]=fa;
	for(int i=1; i<=20; i++)
		if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
		else break;
	for(int Next:edges[Now]) {
		if(Next==fa)continue;
		Dfs(Next,Now,depth+1);
		Size[Now]+=Size[Next];
	}
	Last[Now]=step;
}

int LCA(int a,int b) {
	if(Depth[a]<Depth[b])swap(a,b);
	for(int i=20; i>=0; i--) {
		if(Depth[a]==Depth[b])break;
		if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
	}
	if(a==b)return b;
	for(int i=20; i>=0; i--)
		if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}

void build(vector<int>& a) {
	if(a.front()!=1)a.push_back(1);
	int tmp=a.size();
	for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
	sort(a.begin(),a.end(),cmp);
	auto it=unique(a.begin(),a.end());
	a.erase(it,a.end());
	static int top=0,S[maxn];
	S[++top]=a[0];
	for(int i=1; i<a.size(); i++) {
		int now=a[i];
		while(top>=1) {
			if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
				AddEdge2(S[top],now);
				break;
			}
			top--;
		}
		if(S[top]!=now)S[++top]=now;
	}
}

int Dist(int x,int y) {
	return Depth[x]+Depth[y]-2*Depth[LCA(x,y)];
}

void TreeDp1(int Now) { //从下至上
	c[++step]=Now;
	Remain[Now]=Size[Now];
	for(int Next:tree[Now]) {
		TreeDp1(Next);
		if(!Belong[Next])continue;
		if(!Belong[Now]) {
			Belong[Now]=Belong[Next];
			continue;
		}
		int d1=Dist(Belong[Next],Now),d2=Dist(Belong[Now],Now);
		if(d1<d2||(d1==d2&&Belong[Next]<Belong[Now]))Belong[Now]=Belong[Next];
	}
}

void TreeDp2(int Now) { //从上至下
	for(int Next:tree[Now]) {
		if(!Belong[Next])Belong[Next]=Belong[Now];
		else {
			int d1=Dist(Belong[Now],Next),d2=Dist(Belong[Next],Next);
			if(d1<d2||(d1==d2&&Belong[Now]<Belong[Next]))Belong[Next]=Belong[Now];
		}
		TreeDp2(Next);
	}
}

void Solve(int Now,int Next) {
	int son=Next,mid=Next;
	for(int i=20; i>=0; i--)
		if(Depth[p[son][i]]>Depth[Now])son=p[son][i];
	Remain[Now]-=Size[son];
	if(Belong[Now]==Belong[Next]) {
		Ans[Belong[Now]]+=Size[son]-Size[Next];
		return;
	}
	for(int i=20; i>=0; i--) {
		int tmp=p[mid][i];
		if(Depth[tmp]<=Depth[Now])continue;
		int d1=Dist(Belong[Now],tmp),d2=Dist(Belong[Next],tmp);
		if(d2<d1||(d1==d2&&Belong[Next]<Belong[Now]))mid=tmp;
	}
	Ans[Belong[Now]]+=Size[son]-Size[mid];
	Ans[Belong[Next]]+=Size[mid]-Size[Next];
}

int main() {
	int size=40<<20;//40M
	__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
	memset(p,-1,sizeof(p));
	n=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
		AddEdge(y,x);
	}
	Dfs(1,-1,1);
	q=Get_Int();
	for(int i=1; i<=q; i++) {
		int k=Get_Int();
		a.clear();
		for(int j=1; j<=k; j++) {
			int x=Get_Int();
			a.push_back(x);
			b[j]=x;
			Belong[x]=x;
		}
		sort(a.begin(),a.end(),cmp);
		build(a);
		step=0;
		TreeDp1(1);
		TreeDp2(1);
		for(int j=1; j<=step; j++)
			for(int Next:tree[c[j]])
				Solve(c[j],Next);
		for(int j=1; j<=step; j++)Ans[Belong[c[j]]]+=Remain[c[j]];
		for(int j=1; j<=k; j++)printf("%d ",Ans[b[j]]);
		putchar('\n');
		for(int j=1; j<=step; j++) {
			Ans[c[j]]=Belong[c[j]]=0;
			tree[c[j]].clear();
		}
	}
	exit(0);
}