题目大意
给定一棵$n(n \le 10^5)$个点的无根树,再给定$m(m \le 10^5)$个询问
每次询问给定起点和终点,从起点开始XJB走到终点的期望步数是多少?
定义XJB走为:每次完全随机选择一条出边走出去,可以走回头路
解题报告
如果定义$f_{u,v}$为当前在$u$点,最终走到$v$点的期望步数
那肯定搞一个高斯消元就可以了,但这题数据太大搞不了 QwQ
但我们仔细观察一下,这里的XJB走非常妙啊!目标点、来源点完全不影响决策
于是我们定义$f_u$为这个点走到父亲的期望步数,$g_u$为这个点的父亲走到它的期望步数
那我们就可以推出以下式子:
$$f_u=\deg u + \sum\limits_{v \in son_u}{f_v}$$
$$g_u=\deg fa_u + \sum\limits_{v \in son_{fa_u},v \ne u}{f_v} + g_{fa_{fa_u}}$$
于是我们DFS两遍,然后记个前缀和什么的
询问的时候求出lca然后加加减减就可以辣!
时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = N << 1; int n,m,head[N],nxt[M],to[M]; int in[N],dep[N],fa[N][20]; LL f[N],g[N],PreF[N],PreG[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) { static int E = 1; in[u]++; in[v]++; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline int LCA(int u, int v) { if (dep[u] < dep[v]) swap(u, v); for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u = fa[u][i]; if (u == v) return u; for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } void DFS1(int w, int anc) { fa[w][0] = anc; f[w] = in[w]; dep[w] = dep[anc] + 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != anc) { DFS1(to[i], w); f[w] += f[to[i]]; } } } void DFS2(int w, int anc) { PreF[w] = PreF[anc] + f[w]; PreG[w] = PreG[anc] + g[w]; for (int i=head[w];i;i=nxt[i]) { if (to[i] != anc) { g[to[i]] = f[w] - f[to[i]] + g[w]; DFS2(to[i], w); } } } int main() { n = read(); for (int i=1;i<n;i++) AddEdge(read(),read()); DFS1(1, 1); DFS2(1, 1); for (int j=1;j<20;j++) { for (int i=1;i<=n;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; } } m = read(); for (int i=1,u,v,lca;i<=m;i++) { u = read(); v = read(); lca = LCA(u, v); printf("%lld\n",PreF[u]-PreF[lca]+PreG[v]-PreG[lca]); } return 0; }
Good day! I know this is kind of off topic but I was wondering
which blog platform are you using for this website?
I’m getting sick and 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.
好文章!666,学习了
Appreciate this post. Let me try it out.
First of all I would like to say fantastic blog!
I had a quick question in which I’d like to ask if you do not mind.
I was curious to know how you center yourself and clear your thoughts
prior to writing. I’ve had trouble clearing my mind in getting my
thoughts out there. I truly do enjoy writing but it just seems like the first 10 to 15 minutes are usually wasted
just trying to figure out how to begin. Any recommendations or
tips? Cheers!
These are genuinely fantastic ideas in concerning blogging.
You have touched some nice things here. Any way keep up wrinting.
I every time emailed this blog post page to all my contacts,
since if like to read it after that my links will too.
I’m really enjoying the theme/design of your weblog.
Do you ever run into any web browser compatibility issues?
A few of my blog audience have complained about my
site not operating correctly in Explorer but looks great in Chrome.
Do you have any solutions to help fix this problem?
Wow, awesome blog layout! How long have you been blogging
for? you make blogging look easy. The overall look of your
site is great, let alone the content!
If some one needs expert view concerning blogging after that i recommend him/her to pay a quick visit this web site, Keep up the fastidious
work.
Aw, this was a really good post. Taking a few minutes and
actual effort to generate a good article… but what can I say… I put things off a lot
and never manage to get anything done.
Awesome things here. I’m very happy to peer your article.
Thanks a lot and I’m having a look forward to contact you.
Will you kindly drop me a mail?
My family members always say that I am killing my time here at web, except I know
I am getting experience every day by reading thes good content.
constantly i used to read smaller articles or reviews which also clear their motive,
and that is also happening with this article which I am reading here.
I’m not certain the place you’re getting your information, but
great topic. I needs to spend a while finding out much more or working out more.
Thank you for wonderful info I used to be on the lookout for this information for
my mission.
I was wondering if you ever considered changing the structure of your blog?
Its very well written; I love what youve got to say. But maybe you could
a little more in the way of content so people could connect with
it better. Youve got an awful lot of text for only having one or two pictures.
Maybe you could space it out better?
Hey! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
I’m not that much of a internet reader to be
honest but your blogs really nice, keep it up!
I’ll go ahead and bookmark your site to come back later on. Many
thanks
Hello there, just became aware of your blog through Google,
and found that it’s truly informative. I’m gonna watch out for brussels.
I will be grateful if you continue this in future.
Many people will be benefited from your writing. Cheers!
Howdy! Do you use Twitter? I’d like to follow you if that
would be okay. I’m absolutely enjoying your blog and look forward to new posts.
It is truly a great and helpful piece of info. I am satisfied that
you shared this helpful information with us. Please stay us informed like this.
Thank you for sharing.
I used to be recommended this blog via my cousin. I’m now not certain whether this
post is written via him as no one else recognize such
certain approximately my problem. You’re wonderful! Thank you!
I am truly pleased to glance at this webpage posts which carries lots of useful information,
thanks for providing these kinds of information.
Thanks for a marvelous posting! I certainly enjoyed reading it, you’re a great author.I will
be sure to bookmark your blog and will often come back from now on. I want to encourage one to continue your great job, have a nice day!
Hi, I do think this is an excellent blog. I stumbledupon it 😉 I may come back yet again since i have book
marked it. Money and freedom is the greatest way to change,
may you be rich and continue to help other people.
excellent publish, very informative. I’m wondering why the other
experts of this sector don’t understand this.
You should continue your writing. I am confident, you’ve a great readers’
base already!
bookmarked!!, I love your blog!
Howdy, I think your website may be having web browser compatibility problems.
When I take a look at your website in Safari, it looks fine however, if opening in Internet Explorer, it has some overlapping issues.
I simply wanted to give you a quick heads up! Besides that, fantastic blog!
Hi there to every body, it’s my first pay a visit
of this weblog; this website consists of awesome and genuinely fine material designed for visitors.
I all the time emailed this web site post page to all my associates,
because if like to read it afterward my contacts will too.
I am not positive where you’re getting your info, however good topic.
I must spend a while learning much more or working out more.
Thanks for fantastic info I used to be searching for this information for my mission.
Hi there i am kavin, its my first occasion to commenting anywhere,
when i read this post i thought i could also create comment due
to this good article.
Hello this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you
have to manually code with HTML. I’m starting a blog soon but have no coding knowledge so I wanted to get advice from someone with experience.
Any help would be enormously appreciated!
Wonderful, what a weblog it is! This web site gives valuable
information to us, keep it up.
You really make it appear really easy together with your
presentation however I in finding this topic to be really one thing that I feel
I would never understand. It kind of feels too complex and very broad for
me. I am having a look forward on your next post,
I will attempt to get the grasp of it!
Awesome! Its truly amazing article, I have got much clear idea regarding from this paragraph.
This info is priceless. When can I find out
more?
It’s an remarkable post in support of all the web people; they will take benefit from it I am
sure. plenty of fish natalielise
Hey I am so grateful I found your blog page, I really found you by
mistake, while I was looking on Aol for something
else, Anyways I am here now and would just like to say kudos for a fantastic post and a all round exciting blog (I also love
the theme/design), I don’t have time to go through it all at the moment but I have saved it and also included your RSS feeds,
so when I have time I will be back to read more, Please do keep
up the awesome job.
Hi would you mind stating which blog platform you’re working
with? I’m going to start my own blog in the near future but I’m having
a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different
then most blogs and I’m looking for something completely unique.
P.S My apologies for getting off-topic but I had to ask!
Thanks for some other informative web site. Where else may I get that type of information written in such a perfect approach?
I’ve a mission that I’m simply now operating on, and
I have been on the glance out for such information. natalielise plenty of fish
Nice respond in return of this difficulty with solid arguments and explaining everything
concerning that.
What’s up to all, as I am truly eager of reading this weblog’s post to be updated on a regular basis.
It contains nice stuff. pof natalielise
It’s in reality a great and useful piece of info. I am satisfied that you shared this helpful information with us.
Please stay us up to date like this. Thank you for sharing.
natalielise plenty of fish
Heya! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing a few months of hard work due to no data backup.
Do you have any solutions to prevent hackers?
If you wish for to get a good deal from this article then you have to apply such techniques to your
won weblog.
I do not even know how I ended up here, but I thought this post was great.
I don’t know who you are but definitely you are going to a famous blogger
if you aren’t already 😉 Cheers!
Having read this I believed it was really enlightening. I
appreciate you taking the time and energy to put
this short article together. I once again find myself spending way too much time both
reading and commenting. But so what, it was still worth it!
Wow, wonderful weblog structure! How long have
you been blogging for? you made blogging glance easy.
The total look of your web site is excellent, as
well as the content material!
Great article, totally what I wanted to find.
Hey would you mind stating which blog platform you’re working with?
I’m going to start my own blog in the near future but I’m having a
difficult time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs and I’m looking for something unique.
P.S My apologies for being off-topic but I had to ask!
Hi, Neat post. There is an issue along with your web site
in internet explorer, might check this? IE nonetheless is the
market chief and a big section of people will omit your great writing due to this problem.
Oh my goodness! Incredible article dude! Thank you, However I am experiencing issues with your RSS.
I don’t understand why I am unable to subscribe to it.
Is there anyone else having similar RSS issues? Anyone that knows the answer will you kindly respond?
Thanks!!
This is very interesting, You are a very skilled blogger.
I’ve joined your rss feed and look forward to
seeking more of your wonderful post. Also, I have shared
your site in my social networks!
This is a topic that’s near to my heart… Cheers! Where are your contact details
though?
Spot on with this write-up, I truly believe that this website needs far more attention. I’ll probably be back again to read more, thanks for the info!
you’re really a good webmaster. The website loading velocity is amazing.
It sort of feels that you’re doing any unique trick. Moreover, The contents are masterpiece.
you have performed a magnificent activity on this topic!
It is the best time to make some plans for the future and it’s
time to be happy. I’ve read this post and if I could I want to suggest you few
interesting things or advice. Maybe you can write next articles referring to this article.
I wish to read more things about it!
I like the helpful information you supply for your articles.
I will bookmark your blog and take a look at once more right here frequently.
I am slightly certain I will be told plenty of new stuff proper right here!
Best of luck for the following!
Thanks for sharing your thoughts about minecraft games.
Regards
Ridiculous quest there. What occurred after?
Thanks!
Great site you have got here.. It’s hard to find quality writing like yours these days.
I truly appreciate people like you! Take care!!
I have been exploring for a little bit for any high-quality articles or weblog posts in this sort of house .
Exploring in Yahoo I finally stumbled upon this website.
Reading this info So i am happy to express that I’ve a very good uncanny feeling I discovered exactly what I needed.
I most certainly will make sure to don?t forget this website and provides it a glance regularly.
Hello, i feel that i noticed you visited my blog thus i came to
return the want?.I am trying to find issues to improve my website!I suppose its ok
to make use of some of your ideas!!
What’s up, I would like to subscribe for this website to obtain most recent updates,
thus where can i do it please assist.
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! By the way, how could we communicate?
Way cool! Some extremely valid points! I appreciate you writing this post plus the rest of the website
is extremely good.
It’s a pity you don’t have a donate button! I’d most certainly donate to this fantastic blog!
I suppose for now i’ll settle for bookmarking and adding your RSS feed
to my Google account. I look forward to new updates and
will share this website with my Facebook group.
Talk soon!
What i do not understood is actually how you are now not actually much more neatly-preferred than you might be right
now. You are so intelligent. You already know therefore considerably on the subject of this
subject, made me individually imagine it from so many varied angles.
Its like women and men aren’t interested until it is something to do with Girl gaga!
Your own stuffs nice. All the time care for it up!
I absolutely love your blog and find almost all of your post’s to be what precisely I’m looking for.
Would you offer guest writers to write content available
for you? I wouldn’t mind writing a post or elaborating on a few of the subjects you write with regards to here.
Again, awesome blog!
Can I simply say what a relief to discover a person that truly knows what they’re
talking about online. You definitely know how to bring an issue
to light and make it important. More and more people should look at this and understand this side of
the story. It’s surprising you’re not more popular
since you surely have the gift.
An intriguing discussion is definitely worth comment.
I do think that you should publish more on this subject matter, it might not be
a taboo subject but usually people don’t talk about
these topics. To the next! All the best!!
Way cool! Some very valid points! I appreciate you writing this article
plus the rest of the site is really good.
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from
you! By the way, how could we communicate?
We’re a group of volunteers and starting a new scheme in our community.
Your website offered us with useful info to work on. You have done an impressive task and our entire neighborhood can be grateful to you.
I’ve read several good stuff here. Certainly price bookmarking for revisiting.
I wonder how a lot effort you place to create this type of great informative website.
This text is invaluable. Where can I find out more?
I like the helpful info you provide in your articles.
I’ll bookmark your weblog and check again here
regularly. I’m quite sure I’ll learn many new stuff right here!
Best of luck for the next!
I was able to find good info from your articles.
Hello colleagues, its wonderful post about tutoringand fully explained, keep it up all the time.
Hello I am so delighted I found your webpage, I really found you by accident, while I was
looking on Aol for something else, Anyways I am here now and would just like to
say thanks a lot for a marvelous post and a all round interesting blog
(I also love the theme/design), I don’t have
time to read through it all at the minute but I have bookmarked
it and also added in your RSS feeds, so when I have time I will be
back to read a great deal more, Please do keep up
the fantastic work.
Hello there! I could have sworn I’ve been to this site before but after reading through some of the post
I realized it’s new to me. Anyhow, I’m definitely
glad I found it and I’ll be book-marking and
checking back frequently!
Hi there! I just wanted to ask if you ever have any issues with hackers?
My last blog (wordpress) was hacked and I ended up losing many months of hard work due to no backup.
Do you have any methods to protect against hackers?
I am truly glad to glance at this web site posts which contains tons of helpful information, thanks for providing these statistics.
This article is in fact a pleasant one it helps new net visitors,
who are wishing for blogging.
Hmm it appears like your site ate my first comment (it
was super long) so I guess I’ll just sum it up what
I wrote and say, I’m thoroughly enjoying your blog.
I as well am an aspiring blog writer but I’m still new to the whole thing.
Do you have any tips for inexperienced blog writers?
I’d definitely appreciate it.
Hey there! This post could not be written any better! Reading this post reminds me of my previous room mate!
He always kept talking about this. I will forward this article to him.
Fairly certain he will have a good read. Thanks for sharing!
Hi friends, how is everything, and what you desire to say concerning this piece of writing, in my view its in fact remarkable in favor
of me.
That is a very good tip particularly to those new to the blogosphere.
Brief but very accurate info… Thank you for sharing this one.
A must read post!
I’m not sure why but this weblog is loading incredibly
slow for me. Is anyone else having this issue or is it a problem on my end?
I’ll check back later on and see if the problem still exists.
This is a topic which is near to my heart… Many thanks!
Exactly where are your contact details though?
Hi, everything is going perfectly here and ofcourse every one is sharing information, that’s
genuinely fine, keep up writing.
Thanks to my father who told me regarding this weblog, this
website is genuinely amazing.
Excellent post. I am going through some of these issues as well..
I loved as much as you will receive carried out right here. The sketch is tasteful, your authored material stylish. nonetheless, you command get got an shakiness over that you wish be delivering the following. unwell unquestionably come further formerly again as exactly the same nearly very often inside case you shield this increase.
It is the best time to make some plans for the future and it is time
to be happy. I’ve read this post and if I could I want to suggest you
some interesting things or tips. Maybe you could write next
articles referring to this article. I desire to read even more things about it!
An interesting discussion is worth comment. I think that you should write more on this topic, it might not be a taboo subject but generally people are not enough to speak on such topics. To the next. Cheers
Thank you a lot for sharing this with all of us you really recognize what you are speaking
approximately! Bookmarked. Kindly additionally talk over with my
website =). We may have a hyperlink exchange contract among us
Paragraph writing is also a excitement, if you know after that you can write or else it is complex to write.
Hey I know this is off topic but I was wondering if you knew
of any widgets I could add to my blog that automatically tweet my newest twitter
updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe
you would have some experience with something like this.
Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new updates.
Hello, yeah this piece of writing is in fact nice and I
have learned lot of things from it regarding blogging.
thanks.
Remarkable! Its genuinely amazing article, I have got much clear idea
concerning from this paragraph.
Howdy! Do you use Twitter? I’d like to follow you if that would be okay.
I’m definitely enjoying your blog and look forward
to new updates.
Wonderful web site. Lots of useful info here. I am sending it to some friends ans additionally sharing in delicious. And certainly, thank you on your sweat!
Youre so cool! I dont suppose Ive read anything like this before. So nice to find somebody with some original thoughts on this subject. realy thank you for starting this up. this website is something that is needed on the web, someone with a little originality. useful job for bringing something new to the internet!