【日常小测】随机游走

题目大意

给定一棵$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;
}

90 thoughts to “【日常小测】随机游走”

  1. 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.

  2. 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!

  3. I every time emailed this blog post page to all my contacts,
    since if like to read it after that my links will too.

  4. 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?

  5. 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.

  6. 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?

  7. 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!

  8. 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!

  9. 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!

  10. 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!

  11. 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!

  12. 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.

  13. 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!

  14. 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!

  15. 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.

  16. 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!

  17. 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

  18. 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?

  19. 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!

  20. 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!

  21. 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.

  22. 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!!

  23. 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!

  24. 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!

  25. 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!

  26. 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!

  27. 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.

  28. 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!!

  29. 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!

  30. 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!

  31. 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!

  32. 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.

  33. 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!!

  34. 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.

  35. 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.

  36. 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!

  37. 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?

  38. 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.

  39. 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!

  40. 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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注