【日常小测】随机游走

题目大意

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

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

发表评论

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