【BZOJ 3575】苹果树

Qizy 其他, 树上莫队, 莫队算法, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3757
数据传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/3757.rar

树上莫队的模板题！
真的是好板，只要会树分块就可以写辣！

然而树上莫队有几个地方必须要注意：
1.排序的时候必须以一个点的所在树块的编号为第一关键字，然后第二关键字搞成另一点的DFS序
2.最好把每个询问的两个点中DFS较大的作为第二个点
以上这么做为什么会极大的影响速度并不是太清楚 ╮(╯▽╰)╭ 不过效果真的很好
还有不会的同学，出门左拐去找PoPoQQQ吧：http://blog.csdn.net/popoqqq/article/details/41479829

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50000+9;
const int M = 100000+9;

int head[N],to[M],nxt[M],n,m,col[N],stk[M],top,LIM,dfs_num[M];
int fa[N][17],dep[N],cnt[N],ans,num[N],vout[M],sta[N]; 
struct Query{
	int u,v,a,b,id;
	bool operator < (const Query &B) const {
		return num[u] < num[B.u] || (num[u] == num[B.u] && dfs_num[v] < dfs_num[B.v]);
	}
}query[M];

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;
}

void DFS(int w, int f, int bot) {
	static int block_cnt = 0;
	static int dfs_cnt = 0;
	
	dfs_num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f] + 1; 
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i],w,top);
			if (top - bot >= LIM) {
				block_cnt++;
				while (top > bot) {
					num[stk[top--]] = block_cnt;				
				}
			}
		}
	}
	stk[++top] = w;
	while (!w && top) {
		num[stk[top--]] = block_cnt;
	}
}

inline void update(int id, bool delta) {
	if (cnt[id] == 1 && !delta) ans--;
	else if (!cnt[id] && delta) ans++;
	cnt[id] += delta?1:-1;
}

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

inline void move(int &w, int pur) {
	int lca = LCA(w, pur);
	for (int i=w;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1);
	for (int i=pur;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1);
	w = pur;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

int main(){
	int size = 128 << 20; 
	char *p = (char*)malloc(size) + size;  
	__asm__("movl %0, %%esp\n" :: "r"(p)); 
	
	n = read(); m = read(); LIM = sqrt(n) + 1;
	for (int i=1;i<=n;i++) col[i] = read();
	for (int i=1;i<=n;i++) Add_Edge(read(), read());
	DFS(0,0,0);
	for (int i=1;i<=16;i++) {
		for (int j=0;j<=n;j++) {
			fa[j][i] = fa[fa[j][i-1]][i-1];
		}
	}
	for (int i=1;i<=m;i++) {
		query[i].id = i;
		query[i].u = read(); 
		query[i].v = read();
		query[i].a = read();
		query[i].b = read();
		if (dfs_num[query[i].u] > dfs_num[query[i].v]) {
			swap(query[i].u, query[i].v);
		}
	}
	sort(query+1, query+1+m);
	
	for (int i=1,p1=0,p2=0;i<=m;i++) {
		move(p1, query[i].u);
		move(p2, query[i].v);
		
		int lca = LCA(query[i].v, query[i].u);
		update(col[lca], sta[lca] ^= 1);
		vout[query[i].id] = ans;
		if (query[i].a != query[i].b && cnt[query[i].a] && cnt[query[i].b]) vout[query[i].id]--;
		update(col[lca], sta[lca] ^= 1);
	}
	
	for (int i=1;i<=m;i++) {
		printf("%d\n",vout[i]);
	}
	return 0;
}

164 thoughts to “【BZOJ 3575】苹果树”

  2. hello there and thank you for your info – I have certainly
    picked up something new from right here. I did however expertise several technical issues
    using this website, as I experienced to reload the site a
    lot of times previous to I could get it to load correctly.
    I had been wondering if your web hosting is OK? Not that I’m complaining,
    but sluggish loading instances times will very frequently affect your placement in google and could damage your quality score if ads and marketing with
    Adwords. Well I am adding this RSS to my e-mail and could look out for much more
    of your respective fascinating content. Make sure you
    update this again very soon.

    Reply

  3. Amazing blog! Do you have any suggestions for aspiring writers?
    I’m planning to start my own site soon but I’m a little
    lost on everything. Would you advise starting with
    a free platform like WordPress or go for a paid option? There are so many options out
    there that I’m totally overwhelmed .. Any recommendations?

    Thanks a lot!

    Reply

  7. You can certainly see your skills in the work you write. The
    arena hopes for more passionate writers such as you who
    are not afraid to say how they believe. At all times follow
    your heart.

    Reply

  8. Hey would you mind stating which blog platform you’re
    using? I’m going to start my own blog in the near future but I’m
    having a hard time selecting between BlogEngine/Wordpress/B2evolution and Drupal.

    The reason I ask is because your design and style seems different then most blogs and I’m looking for something completely unique.
    P.S Apologies for being off-topic but I had to ask!

    Reply

  9. Very nice post. I simply stumbled upon your weblog and wanted to say that I have really loved browsing your weblog posts.
    In any case I will be subscribing for your feed and I’m hoping you write again very soon!

    Reply

  13. Thank you for every other great article. The place else may just anybody get that kind of info in such a perfect approach of writing?
    I’ve a presentation subsequent week, and
    I’m on the search for such info.

    Reply

  21. Hey There. I found your blog the usage of msn. This is a really smartly written article.
    I’ll make sure to bookmark it and return to learn more of your useful information. Thank you for the
    post. I will definitely comeback. natalielise pof

    Reply

  22. You actually make it seem really easy with your presentation but I find this
    matter to be actually something which I think I might never understand.
    It kind of feels too complex and very vast for me. I am having a look ahead on your next submit,
    I will try to get the dangle of it!

    Reply

  23. I used to be suggested this website through
    my cousin. I’m not sure whether this submit is written via him as
    nobody else realize such distinct about my difficulty.

    You are incredible! Thank you!

    Reply

  24. It’s amazing to pay a visit this site and reading the views of all mates on the topic of this paragraph,
    while I am also keen of getting knowledge.

    Reply

  26. Hello there! I simply would like to give you a big thumbs up for your great information you have got right
    here on this post. I will be coming back to your web site for more soon.

    Reply

  34. Wow that was unusual. I just wrote an incredibly long comment but after
    I clicked submit my comment didn’t appear. Grrrr…
    well I’m not writing all that over again. Anyhow, just
    wanted to say wonderful blog!

    Reply

  35. I don’t even know how I ended up here, but I thought this post was great.
    I do not know who you are but certainly you are going to a famous blogger if you aren’t already 😉 Cheers!

    Reply

  36. I’m really impressed with your writing skills and also with the
    layout on your weblog. Is this a paid theme or did you customize it yourself?
    Anyway keep up the excellent quality writing, it’s rare to see a great
    blog like this one these days.

    Reply

  37. Thank you for the good writeup. It in truth was a leisure account
    it. Glance advanced to far delivered agreeable from you!
    By the way, how could we keep up a correspondence?

    Reply

  38. Nice blog here! Also your website loads up fast!
    What host are you using? Can I get your affiliate link to your host?
    I wish my website loaded up as quickly as yours lol

    Reply

  39. Howdy! I could have sworn I’ve visited this site before but after going through
    some of the posts I realized it’s new to me. Nonetheless, I’m definitely pleased I discovered it and I’ll be bookmarking it
    and checking back often!

    Reply

  40. When someone writes an piece of writing he/she maintains the thought
    of a user in his/her mind that how a user can know it.
    So that’s why this post is outstdanding. Thanks!

    Reply

  46. It’s actually a cool and useful piece of information. I’m
    satisfied that you shared this helpful information with us.
    Please keep us informed like this. Thanks for sharing.

    Reply

  47. Hello There. I discovered your blog the use of msn.
    That is a really smartly written article. I’ll make sure to bookmark it and come back to read extra of your
    useful information. Thanks for the post. I’ll definitely return.

    Reply

  48. I’d like to thank you for the efforts you’ve put in penning this website.
    I am hoping to view the same high-grade blog posts from you in the future as well.
    In fact, your creative writing abilities has encouraged me to get my own website now ;
    )

    Reply

  49. Hello there! I know this is somewhat off topic but I was
    wondering which blog platform are you using for this website?
    I’m getting tired of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
    I would be great if you could point me in the direction of a good
    platform.

    Reply

  50. We’re a group of volunteers and opening a new scheme in our
    community. Your site offered us with valuable info to work on.
    You’ve performed a formidable job and our entire neighborhood will
    likely be thankful to you.

    Reply

  51. It’s a pity you don’t have a donate button! I’d definitely donate to this brilliant blog!

    I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google
    account. I look forward to brand new updates and will talk about this blog
    with my Facebook group. Chat soon!

    Reply

  53. A motivating discussion is definitely worth comment.
    There’s no doubt that that you ought to publish more about
    this subject matter, it might not be a taboo subject but typically
    folks don’t discuss such issues. To the next!
    Kind regards!!

    Reply

  61. fantastic put up, very informative. I wonder why the other specialists of this sector do not understand this.

    You should proceed your writing. I’m confident, you have a great readers’ base
    already!

    Reply

  64. Hello there! This post couldn’t be written any better! Looking at this article reminds me of my previous roommate!

    He always kept talking about this. I will forward this post to him.
    Fairly certain he will have a very good read. Thank you for sharing!

    Reply

  66. You really make it seem really easy along with your presentation however I to find this matter to be really one thing which I
    think I would never understand. It kind of feels too complicated and
    extremely extensive for me. I’m looking ahead in your next publish, I’ll try to get the dangle of it!

    Reply

  77. Hi exceptional blog! Does running a blog similar to this take a great deal of work?
    I have virtually no expertise in computer programming but
    I had been hoping to start my own blog in the near future.
    Anyhow, if you have any recommendations or techniques for new blog owners please share.
    I understand this is off subject however I simply had to
    ask. Cheers!

    Reply

  79. My coder is trying to persuade me to move to .net from PHP.
    I have always disliked the idea because of
    the costs. But he’s tryiong none the less. I’ve been using
    WordPress on a number of websites for about
    a year and am concerned about switching to another platform.
    I have heard fantastic things about blogengine.net.
    Is there a way I can transfer all my wordpress content into it?
    Any help would be greatly appreciated!

    Reply

  80. Woah! I’m really enjoying the template/theme of this website.
    It’s simple, yet effective. A lot of times it’s very hard
    to get that “perfect balance” between superb usability and visual appeal.
    I must say you have done a great job with this. Also, the blog loads super fast for me
    on Internet explorer. Superb Blog!

    Reply

  101. Hello! I’m at work browsing your blog from
    my new iphone 4! Just wanted to say I love reading through your blog and look
    forward to all your posts! Keep up the superb work!

    Reply

  110. I do agree with all the ideas you have offered in your post.
    They’re really convincing and can certainly work.
    Still, the posts are too brief for beginners.

    Could you please prolong them a bit from subsequent
    time? Thank you for the post.

    Reply

  120. My spouse and I stumbled over here by a different web address and thought I may as well check things out. I like what I see so now i’m following you. Look forward to looking at your web page repeatedly.

    Reply

  136. I don’t know if it’s just me or if perhaps everybody else encountering issues with your site.
    It looks like some of the written text on your posts are running off the screen. Can someone else please
    provide feedback and let me know if this is happening to
    them too? This might be a issue with my web browser because I’ve
    had this happen previously. Thank you

    Reply

  140. “4 Songs for the Club” Is a 4 song CD-EP from B-Rock, For Dj’s and Bars and Dance clubs ..”Dance”Features Rockman doing the electronic Vocals on the Chorus. A hand clapping song to get people on tha dance floor ….”Mix It With Tha Water”. Features B-Rocks Team member Pif .. Tha song is an urban street tale with a great Trap Beat….”I Like It Straight” is Bound to be a New Club/ Bar Anthem for the DJ’s to get the crowds up on their feet and to get another drink..LOL…and “Crack Them bottle (Get Fucked Up)” well that’s a story that all party goers live on the weekend! … 4 Dance Hits 4 tha Club.. a great EP for any DJ to have

    Reply

  141. Good way of explaining, and pleasant piece
    of writing to obtain facts regarding my presentation topic,
    which i am going to deliver in institution of higher education.

    Reply

  142. Wow! This blog looks just like my old one! It’s on a entirely different subject but it has pretty much the same layout and design. Wonderful choice
    of colors!

    Reply

  156. Excellent goods from you, man. I’ve have in mind your stuff previous to and you are simply too
    magnificent. I actually like what you have acquired right here,
    certainly like what you are saying and the way in which wherein you assert it.
    You’re making it entertaining and you continue to care for to
    keep it smart. I can not wait to learn much more from
    you. That is really a great website.

    Reply

Leave a Reply

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