题目传送门: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; }
This piece of writing is genuinely a nice one it assists new the web visitors, who are wishing for blogging.
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.
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!
This post will help the internet people for creating new website or even a weblog from start to
end.
Hello there, You have done a fantastic job.
I’ll definitely digg it and personally suggest to my friends.
I’m sure they’ll be benefited from this site.
Because the admin of this site is working, no doubt very soon it will be famous, due to its quality contents.
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.
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!
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!
What a information of un-ambiguity and preserveness of precious experience about unexpected emotions.
I take pleasure in, cause I found exactly
what I was having a look for. You’ve ended my four day long hunt!
God Bless you man. Have a great day. Bye
Hi there i am kavin, its my first occasion to commenting
anywhere, when i read this piece of writing i thought
i could also make comment due to this brilliant
post.
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.
I am regular reader, how are you everybody? This paragraph posted at this
web site is in fact fastidious.
Your method of describing the whole thing in this post is really fastidious, every one can effortlessly be aware of it,
Thanks a lot.
You ought to take part in a contest for one of the finest blogs on the internet.
I am going to highly recommend this web site!
This article will help the internet users for setting up new web
site or even a blog from start to end.
Whoa! This blog looks just like my old one! It’s on a entirely different topic but it has pretty much the same layout and design. Excellent choice of colors!
Ahaa, its good dialogue about this post at this place at this weblog, I have read all that,
so now me also commenting here.
What a material of un-ambiguity and preserveness of precious knowledge
regarding unexpected feelings.
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
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!
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!
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.
I have read so many content concerning the blogger
lovers however this paragraph is genuinely a good piece of writing, keep it up.
natalielise plenty of fish
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.
Wonderful website. Lots of useful information here. I am sending it to
a few friends ans also sharing in delicious. And obviously, thank
you in your effort! plenty of fish natalielise
Very descriptive article, I liked that a lot. Will there be a part 2?
If some one desires to be updated with latest technologies therefore he must be pay a visit
this site and be up to date everyday.
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! However, how can we communicate?
Excellent article! We are linking to this particularly great content on our website.
Keep up the good writing.
I couldn’t resist commenting. Perfectly written!
It’s going to be ending of mine day, however before finish I am reading this
impressive post to improve my experience.
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!
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!
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.
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?
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
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!
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!
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you!
By the way, how could we communicate?
If some one needs to be updated with latest technologies after that he must be pay a quick visit this web page and be up to date everyday.
If some one wants to be updated with hottest technologies then he must be go to see this web page and be up to date
daily.
Excellent post however I was wondering if you could write a litte more on this subject?
I’d be very thankful if you could elaborate a
little bit more. Thanks!
Hi there to every one, the contents existing at this web site are truly awesome for people experience, well, keep up the good work fellows.
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.
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.
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 ;
)
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.
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.
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!
That is a good tip especially to those fresh to
the blogosphere. Simple but very precise info… Many thanks for sharing this one.
A must read article!
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!!
I like the valuable info you provide in your articles. I’ll bookmark your blog and check again here
regularly. I’m quite sure I’ll learn many new stuff right here!
Best of luck for the next!
Heya i’m for the first time here. I came across this
board and I find It really useful & it helped me out much.
I hope to give something back and aid others like you aided me.
Enjoyed every bit of your blog post.Much thanks again. Great.
I couldn’t refrain from commenting. Very well written!
Hello to every body, it’s my first go to see of this website; this web site carries remarkable and really fine material designed for visitors.
Hey, thanks for the post.Really thank you! Fantastic.
Im obliged for the article.Really looking forward to read more. Much obliged.
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!
Really informative blog article.Thanks Again. Want more.
Thanks again for the blog.Thanks Again. Really Cool.
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!
Major thankies for the article.Really thank you! Much obliged.
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!
Thanks again for the post.Much thanks again. Great.
I really liked your post.Really thank you! Really Cool.
I couldn’t resist commenting. Well written!
Thank you for your blog.Really looking forward to read more.
Im obliged for the blog.Really looking forward to read more. Fantastic.
Great, thanks for sharing this article.Thanks Again. Really Great.
Really enjoyed this article.Much thanks again. Want more.
Muchos Gracias for your blog.Much thanks again. Fantastic.
Thank you ever so for you blog. Great.
Thanks for the blog.Thanks Again. Much obliged.
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!
Normally I do not read post on blogs, however I would like to say that this write-up very pressured me to check out
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!
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!
Fantastic blog article.Thanks Again. Really Cool.
I truly appreciate this article.Really thank you! Really Cool.
I was looking at some of your content on this site and I conceive this internet site is very instructive! Retain posting.
It’s amazing for me to have a web site, which is good in favor of my know-how. thanks admin
Enjoyed every bit of your post.Really thank you! Really Great.
Appreciate you sharing, great post. Really Great.
I truly appreciate this post.Thanks Again. Want more.
Thank you for your article. Will read on…
Major thanks for the blog.Really thank you! Really Cool.
I loved your post.Really looking forward to read more. Fantastic.
I value the blog post. Want more.
Appreciate you sharing, great blog article.Really thank you! Keep writing.
Hey, thanks for the blog post. Want more.
Your writing taste has been surprised me. Thank you, quite nice post.
Very good blog post.Really looking forward to read more. Awesome.
Thank you for your blog post.Thanks Again. Fantastic.
Thank you ever so for you article post.Much thanks again. Want more.
Im thankful for the blog post.Much thanks again. Awesome.
I loved your blog article.Really looking forward to read more. Great.
Im thankful for the blog post. Will read on…
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!
Im grateful for the blog post. Want more.
Thanks so much for the post.Really thank you! Much obliged.
Enjoyed every bit of your blog post.Much thanks again. Great.
If you would like to improve your familiarity only keep visiting this site and be updated with the most recent information posted
here.
Very informative blog article.Really thank you! Cool.
Thanks-a-mundo for the article.Thanks Again. Really Great.
Awesome blog article.Really thank you! Fantastic.
I am so grateful for your blog post.Really looking forward to read more. Will read on…
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.
Thanks so much for the post. Keep writing.
Really appreciate you sharing this blog post.Much thanks again. Will read on…
Thanks again for the post.Really looking forward to read more.
Really appreciate you sharing this blog post.Really thank you! Great.
Muchos Gracias for your article post.Really thank you! Really Great.
Appreciate you sharing, great blog article.Thanks Again. Awesome.
Thank you ever so for you article. Fantastic.
Very neat article. Keep writing.
Hello, yup this piece of writing is really nice and I
have learned lot of things from it concerning blogging. thanks.
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.
Thanks for the blog article.Much thanks again. Awesome.
Thanks for sharing, this is a fantastic article. Great.
Everyone loves what you guys are up too. This type of clever work and exposure!
Keep up the amazing works guys I’ve added you guys to our blogroll.
Thank you for your article post.Thanks Again. Want more.
Thank you ever so for you blog post. Fantastic.
Thank you for your article post.Much thanks again. Fantastic.
Thanks for this amazing Post dear, I like your blog.
Im grateful for the article post.Thanks Again. Fantastic.
I value the blog.Really thank you! Keep writing.
Thanks-a-mundo for the blog article.Really thank you!
Thank you ever so for you blog post. Awesome.
I think this is a real great blog.Really looking forward to read more. Really Great.
I truly appreciate this article. Awesome.
A big thank you for your article post.Thanks Again. Cool.
Very informative article.Thanks Again.
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
Thanks for sharing your thoughts about match.com free trial.
Regards
Hi to every one, since I am really eager of reading
this website’s post to be updated daily. It carries fastidious material.
I’m gone to tell my little brother, that he should also pay a visit this weblog on regular basis to obtain updated from hottest gossip.
“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
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.
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!
Appreciate you sharing, great blog post.Much thanks again. Really Cool.
Thanks again for the blog article.
Major thankies for the blog article.Really thank you! Keep writing.
Great, thanks for sharing this blog post.Thanks Again. Much obliged.
Say, you got a nice article.Much thanks again. Cool.
I cannot thank you enough for the blog post.Much thanks again. Really Great.
Fastidious response in return of this difficulty with solid arguments and telling all
on the topic of that.
Thank you for your blog.Thanks Again. Cool.
Enjoyed every bit of your article.Really looking forward to read more. Keep writing.
Thanks again for the blog.Really thank you! Keep writing.
Very good blog post.Thanks Again. Want more.
Fantastic post.Really looking forward to read more. Great.
A big thank you for your post.Really thank you! Fantastic.
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.
I value the article post. Fantastic.
Hi there i am kavin, its my first time to commenting
anyplace, when i read this article i thought i could also make comment due to this good
piece of writing.
There’s certainly a lot to find out about this subject.
I love all of the points you’ve made.
You have brought up a very wonderful points, regards for the post.
A round of applause for your article post. Great.
A big thank you for your article.Really thank you! Fantastic.
wow, awesome article.Thanks Again. Great.
I truly appreciate this blog article. Really Great.