【BZOJ 3572】[Hnoi2014] 世界树

Qizy 树, 虚树, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3572
数据生成器：http://paste.ubuntu.com/23376760/

一看数据范围肯定知道是虚树辣！
题解的话，让我们召唤曹清华：http://blog.csdn.net/jzhang1/article/details/50630194
然后就是恶心的码代码环节…..
人太懒，于是带了两个log，慢成翔 qwq

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int N = 300000+9;
const int M = N << 1;
const int INF = 1000000000;

int head[N],nxt[M],to[M],T,n,m,tot,num[N],blg[N],p[N],sz[N];
int stk[N],top,dep[N],fa[N][18],size[N],vis[N],vout[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v) {to[++T] = v; nxt[T] = head[u]; head[u] = T;}
inline void Add_Edge(int u, int v) {AddEdge(u,v);AddEdge(v,u);}
inline bool CMP(int a, int b) {return num[a] < num[b];}

void DFS(int w, int f) {
	static int dfs_cnt = 0; num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f]+1; size[w] = 1;
	for (int i=1;i<=17;i++) fa[w][i] = fa[fa[w][i-1]][i-1];
	
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
			size[w] += size[to[i]];
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca]*2;
}

inline void Build(int root) {
	p[++tot] = root; 
	stk[top=1] = root;
	sz[root] = n;
	
	for (int i=1,w,lca;i<=m;i++) {
		w = p[i]; lca = LCA(stk[top],w);
		while (dep[stk[top]] > dep[lca]) {
			if (dep[stk[top-1]] < dep[lca]) 
				AddEdge(lca, stk[top]);
			else 
				AddEdge(stk[top-1], stk[top]);
			top--;
		}
		if (lca != stk[top]) {
			stk[++top] = lca;
			p[++tot] = lca;
			sz[lca] = size[lca] - 1;
		} 
		if (w != stk[top]) {
			stk[++top] = w;
			sz[w] = size[w] - 1;
		}
	}
	for (int i=1;i<top;i++) 
		AddEdge(stk[i], stk[i+1]);
}

void prework_1(int w, int up) {
	blg[w] = vis[w]?w:up; 
	for (int i=head[w];i;i=nxt[i]) {
		prework_1(to[i], vis[w]?w:up);
		if (~blg[to[i]]) {
			int len1 = (~blg[w]?abs(dep[blg[w]] - dep[w]):INF);
			int len2 = abs(dep[blg[to[i]]] - dep[w]);
			if (!~blg[w] || len1 > len2 || (len1 == len2 && blg[to[i]] < blg[w])) 
				blg[w] = blg[to[i]];
		}
	}
}

void prework_2(int w) {
	for (int i=head[w];i;i=nxt[i]) {
		if (blg[w] != blg[to[i]]) {
			int len1 = dis(blg[w], to[i]);
			int len2 = dis(blg[to[i]], to[i]);
			if (len1 < len2 || (len1 == len2 && blg[w] < blg[to[i]])) 
				blg[to[i]] = blg[w];
		}
		prework_2(to[i]);
	}
}

void solve(int w) {
	for (int i=head[w],len,cur;i;i=nxt[i]) {
		top = to[i];
		for (int j=17;~j;j--) {
			if (dep[fa[top][j]] > dep[w]) 
				top = fa[top][j];
		}
		sz[w] -= size[top];
		
		if (blg[w] == blg[to[i]]) {
			vout[vis[blg[w]]] += size[top] - size[to[i]] + 1;
		} else {
			cur = to[i];
			for (int j=17;~j;j--) {
				if (dis(fa[cur][j],blg[w]) > dis(blg[to[i]], fa[cur][j])) 
					cur = fa[cur][j];
			}
			vout[vis[blg[to[i]]]] += size[cur] - size[to[i]] + 1;
			if (dep[fa[cur][0]] > dep[w] && dis(fa[cur][0], blg[w]) == dis(fa[cur][0], blg[to[i]])){
				vout[vis[min(blg[w], blg[to[i]])]] += size[fa[cur][0]] - size[cur];
				vout[vis[blg[w]]] += size[top] - size[fa[cur][0]];
			} else {
				vout[vis[blg[w]]] += size[top] - size[cur];
			}
		}
		solve(to[i]);
	}
	vout[vis[blg[w]]] += sz[w];
}

int main(){
	n = read();
	for (int i=1;i<n;i++) 
		Add_Edge(read(),read()); 
	DFS(1,1);
	
	T = 0; memset(head,0,sizeof(head));
	for (int q=read(),lca;q;q--) {
		m = tot = read(); 
		lca = p[1] = read();
		vis[p[1]] = 1; vout[1] = 0;
		for (int i=2;i<=m;i++) {
			vis[p[i]=read()] = i;
			lca = LCA(lca, p[i]);
			vout[i] = 0;
		}
		sort(p+1, p+1+m, CMP);
		
		Build(lca);
		prework_1(lca,-1);
		prework_2(lca);
		solve(lca);
		for (int i=1;i<=m;i++) {
			printf("%d ",vout[i]);
		} putchar('\n');
		
		for (int i=1;i<=tot;i++) {
			vis[p[i]] = head[p[i]] = 0;
		} T = 0;
	}
	return 0;
}

194 thoughts to “【BZOJ 3572】[Hnoi2014] 世界树”

  31. My brother suggested I may like this web site. He was totally right.
    This put up actually made my day. You can not believe simply how much time I had
    spent for this info! Thanks!

    Reply

  41. Hey there, You’ve done a great job. I will definitely digg it and personally suggest to my friends.
    I am confident they’ll be benefited from this website.

    Reply

  53. I’ve learn several excellent stuff here. Certainly worth bookmarking for
    revisiting. I surprise how a lot effort you place to create
    this type of fantastic informative web site.

    Reply

  64. Hi just wanted to give you a quick heads up and let you know a few of the images aren’t loading correctly.
    I’m not sure why but I think its a linking
    issue. I’ve tried it in two different internet browsers and both show the same results.

    Reply

  86. Just desire to say your article is as surprising. The
    clearness in your post is just nice and i could assume
    you are an expert on this subject. Fine with your permission allow me to grab your RSS feed to keep
    updated with forthcoming post. Thanks a million and please carry on the rewarding work.

    Reply

  98. I’m not sure why but this site is loading extremely slow for me.
    Is anyone else having this issue or is it a problem on my end?
    I’ll check back later and see if the problem still exists.

    Reply

  102. Hey great website! Does running a blog like
    this take a large amount of work? I have very little understanding of programming however I was hoping to
    start my own blog soon. Anyhow, should you have any recommendations or techniques for new blog owners please
    share. I know this is off topic but I simply needed
    to ask. Kudos!

    Reply

  152. Undeniably imagine that that you said. Your favourite reason seemed to be on the
    net the easiest factor to keep in mind of. I say to you, I
    definitely get annoyed while people consider concerns that they just don’t know
    about. You managed to hit the nail upon the highest and defined out the whole thing with
    no need side-effects , other people could take a signal.
    Will likely be again to get more. Thank you

    Reply

  153. hey there and thank you for your info – I have definitely picked up something new from proper here. I did alternatively expertise several technical points using this site, since I skilled to reload the web site many times previous to I may just get it to load properly. I have been thinking about in case your web host is OK? Not that I’m complaining, however sluggish loading instances instances will sometimes impact your placement in google and could injury your high-quality score if advertising and ***********|advertising|advertising|advertising and *********** with Adwords. Anyway I’m including this RSS to my e-mail and could look out for a lot more of your respective intriguing content. Make sure you update this again soon..

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *