BZOJ 3572: [Hnoi2014]世界树 （虚树，DP）

BZOJ 3572

题意：一颗树，给了一些指定的点，树上的点离那个给点的点近就属于哪个点，距离相等属于编号小的。 问每个给定的点可以管辖多少个点。 参考链接：http://user.qzone.qq.com/251815992/blog/1407315782 http://lazycal.logdown.com/posts/202331-bzoj3572 虚树：包含了给定点，并收缩了不分叉边的连通子图。

3572: [Hnoi2014]世界树

Time Limit: 20 Sec Memory Limit: 512 MB Submit: 226 Solved: 145 [Submit][Status]

Description

世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。 世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地a和b之间有道路，b和c之间有道路，因为每条道路长度为1而且又不可能出现环，所卧a与c之间的距离为2。 出于对公平的考虑，第i年，世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x（x为种族的编号），如果距离该种族最近的临时议事处为y（y为议事处所在聚居地的编号），则种族x将接受y议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则y为其中编号最小的临时议事处）。 现在国王想知道，在q年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。

Input

第一行为一个正整数n，表示世界树中种族的个数。 接下来n-l行，每行两个正整数x，y，表示x聚居地与y聚居地之间有一条长度为1的双 向道路。接下来一行为一个正整数q，表示国王询问的年数。 接下来q块，每块两行： 第i块的第一行为1个正整数m[i]，表示第i年授权的临时议事处的个数。 第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。

Output

输出包含q行，第i行为m\[i\]个整数，该行的第j(j=1，2…，，m\[i\])个数表示第i年被授权的聚居地h\[j\]的临时议事处管理的种族个数。

Sample Input

10 21 32 43 54 61 73 83 94 10 1 5 2 61 5 27369 1 8 4 87103 5 29358

Sample Output

19 31411 10 1135 41311

HINT

N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000

Source

这题可谓当年2013changchun区域赛的J题的加强版。   虚树上进行DP的方法非常经典。

/* ***************

Author        :kuangbin

Created Time  :2014/8/18 19:55:13

File Name     :E:\2014ACM\BZOJ\bzoj3572.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 300010;

const int DEG = 20;

struct Edge{

	int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

void init(){

	tot = 0;

	memset(head,-1,sizeof(head));

}

void addedge(int u,int v){

	edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;

}

int fa[MAXN][DEG];

int deg[MAXN];

void BFS(int root){

	queue<int>q;

	deg[root] = 0;

	fa[root][0] = root;

	q.push(root);

	while(!q.empty()){

		int u = q.front();

		q.pop();

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

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

		for(int i = head[u];i != -1;i = edge[i].next){

			int v = edge[i].to;

			if(v == fa[u][0])continue;

			deg[v] = deg[u] + 1;

			fa[v][0] = u;

			q.push(v);

		}

	}

}

int LCA(int u,int v){

	if(deg[u] > deg[v])swap(u,v);

	int hu = deg[u], hv = deg[v];

	int tu = u, tv = v;

	for(int det = hv-hu, i = 0; det;det>>=1,i++)

		if(det&1)

			tv = fa[tv][i];

	if(tu == tv)return tu;

	for(int i = DEG-1;i >= 0;i--){

		if(fa[tu][i] == fa[tv][i])

			continue;

		tu = fa[tu][i];

		tv = fa[tv][i];

	}

	return fa[tu][0];

}

int DFN[MAXN],Index;

int size[MAXN];

void dfs(int u){

	DFN[u] = ++Index;

	size[u] = 1;

	for(int i = head[u];i != -1;i = edge[i].next){

		int v = edge[i].to;

		if(v == fa[u][0])continue;

		dfs(v);

		size[u] += size[v];

	}

}

int find(int u,int d){//找到u往上的祖先中深度为d的点

	for(int i = DEG-1;i >= 0;i--)

		if(deg[fa[u][i]] >= d)

			u = fa[u][i];

	return u;

}

int h[MAXN],th[MAXN];

int st[MAXN],father[MAXN];

int t[MAXN],val[MAXN];

int ans[MAXN],w[MAXN];

pair<int,int>g[MAXN];

bool cmp(int i,int j){

	return DFN[i] < DFN[j];

}

void solve(int n){

	int m;

	int tot = 0;

	scanf("%d",&m);

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

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

		th[i] = h[i];//备份

		t[++tot] = h[i];

		g[h[i]] = make_pair(0,h[i]);

		ans[h[i]] = 0;

	}

	sort(h+1,h+m+1,cmp);

	int top = 0;

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

		if(!top)father[st[++top] = h[i]] = 0;

		else {

			int p = h[i], lca = LCA(h[i],st[top]);

			for(;deg[st[top]] > deg[lca];--top)

				if(deg[st[top-1]] <= deg[lca])

					father[st[top]] = lca;

			if(st[top] != lca){

				t[++tot] = lca;

				g[lca] = make_pair(0x3f3f3f3f,0);

				father[lca] = st[top];

				st[++top] = lca;

			}

			father[p] = lca;

			st[++top] = p;

		}

	}

	sort(t+1,t+tot+1,cmp);

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

		int p = t[i];

		val[p] = size[p];

		if(i > 1)w[p] = deg[p] - deg[father[p]];

	}

	for(int i = tot;i > 1;i--){

		int p = t[i];

		g[father[p]] = min(g[father[p]],make_pair(g[p].first+w[p],g[p].second));

	}

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

		int p = t[i];

		g[p] = min(g[p],make_pair(g[father[p]].first+w[p],g[father[p]].second));

	}

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

		int p = t[i], f = father[p];

		if(i == 1)ans[g[p].second] += n-size[p];

		else {

			int x = find(p,deg[f]+1), sum = size[x]-size[p];

			val[f] -= size[x];

			if(g[f].second == g[p].second)ans[g[p].second] += sum;

			else {

				int mid = deg[p] - ((g[f].first + g[p].first + w[p])/2 - g[p].first);

				if((g[f].first + g[p].first + w[p])%2 == 0 && g[p].second > g[f].second)++mid;

				int y = size[find(p,mid)] - size[p];

				ans[g[p].second] += y;

				ans[g[f].second] += sum-y;

			}

		}

	}

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

		ans[g[t[i]].second] += val[t[i]];

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

		printf("%d ",ans[th[i]]);

	}

	printf("\n");

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n;

	while(scanf("%d",&n) == 1){

		init();

		int u,v;

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

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

			addedge(u,v);

			addedge(v,u);

		}

		BFS(1);

		Index = 0;

		dfs(1);

		int Q;

		scanf("%d",&Q);

		while(Q--)solve(n);

	}

    return 0;

}