仓鼠找sugar II

题目描述

小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a，是任意的）他的基友卧室（b，还是任意的）。（注意，a有可能等于b。）然而小仓鼠学OI学傻了，不知道怎么怎么样才能最短的走到目的地。于是他只能随便乱走。当他在每一个节点时，等概率到这个点的母亲或者所有孩子节点（例如这个节点有一个母亲节点和两个子节点，那么下一步走到这3个节点的概率都是1/3）。一但走到了他基友的卧室，就会停下。

现在小仓鼠希望知道，他走到目的地时，走的步数的期望。这个期望本来是一个有理数，但是为了避免误差，我们要求对这个有理数取模，%998244353。

下面是“分数”模运算的定义：

b, m互质

k = a/b (mod m) <=> kb = a (mod m)

这里求 x = 1/17 (mod 2668)

<=>

17x = 1 (mod 2668)

<=>

17x = 2668k + 1 （k∈整数）

取合适的k使得17|(2668k+1) 这里刚好17 | (2668 + 1)

所以k = 1, x = (2668+1)/17 = 157

当然，当k = 1 + 17n 时，

x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n

也符合条件（n任意整数）

但如果限定 2668 > x > 0，x是唯一的。

小仓鼠那么弱，还要天天被JOHNKRAM大爷虐，请你快来救救他吧！

输入输出格式

输入格式：

第一行一个正整数n，表示这棵树节点的个数。

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

输出格式：

一个整数，表示取模后的答案。

输入输出样例

输入样例#1：

3

1 2

1 3

输出样例#1：

110916041

说明

对于30%的数据 n<=5；

对于50%的数据 n<=5000；

对于所有数据 n<=100000。

样例解释

期望是16/9

如果a在叶子 b在根，E1=1。有2种情况。

如果a在根，b在叶子。E2=1/2+31/4+51/8...=3。有2种情况。

如果a和b都在不同的叶子，E3=E2+1。有2种情况。

如果a=b，E4=0，有3种情况。

所以期望是16/9，有理数取模后就是输出。

题解

期望

可以考虑把每条边的贡献拆成两部分

一部分是\(f[u]\)表示从u走到ta的父亲的期望距离

另一部分是\(g[u]\)表示从u的父亲走到u的期望距离

然后就可以求出从u走到父亲的期望\(f[u] = \frac{1}{d[u]} * 1 + \frac{1}{d[u]} * \sum_{son[u]}{(1 + f_{son[u]} + f[u])}\)

然后两遍同时乘\(d[u]\)

移一下项\(f[u] = d[u] + \sum_{son[u]}{f_{son[u]}}\)

然后再求出从v的父亲u走到v的期望\(g[v] = \frac{1}{d[u]} * 1 + \frac{1}{d[u]} * (1 + g[u] + g[v]) + \frac{1}{d[u]} * \sum_{son[u]≠v}{(1 + f_{son[u]} + g[v])}\)

同时乘\(d[u]\)然后移项得\(g[v]=g[u]+\sum_{son[u]≠v}{f_{son[u]}}+d[u]\)

这样求出\(f[]\)和\(g[]\)以后再Dfs一遍统计答案

对于一个点,ta对答案的贡献是ta的子树内的每个节点全部到外面的任意一个节点去然后外面的任意一个节点到子树里的任意一个节点来的期望

即\(size[u] * (n-size[u]) * (f[u]+g[u])\)

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

# define int long long

const int M = 100005 ;

const int mod = 998244353 ;

using namespace std ;

inline int read() {

	char c = getchar() ; int x = 0 , w = 1 ;

	while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }

	while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }

	return x*w ;

}

int n ;

int hea[M] , num ;

int d[M] , size[M] ;

int f[M] , g[M] , t[M] , Ans ;

struct E {

	int Nxt , to ;

} edge[M << 1] ;

inline void add_edge(int from , int to) {

	edge[++num].Nxt = hea[from] ;

	edge[num].to = to ;

	hea[from] = num ;

}

void exgcd(int a , int b , int &x , int &y) {

	if(b == 0) { x = 1 , y = 0 ; return ; }

	exgcd(b , a % b , x , y) ;

	int tmp = x ; x = y ; y = tmp - a / b * y ;

}

inline int inv(int a) {

	int x , y ; exgcd(a , mod , x , y) ;

	return (x + mod) % mod ;

}

void Dfs1(int u , int father) {

	f[u] = d[u] ;

	for(int i = hea[u] ; i ; i = edge[i].Nxt) {

		int v = edge[i].to ;

		if(v == father) continue ;

		Dfs1(v , u) ;

		f[u] += f[v] ;

	}

}

void Dfs2(int u , int father) {

	int ret = 0 ;

	for(int i = hea[u] ; i ; i = edge[i].Nxt) {

		int v = edge[i].to ;

		if(v == father) continue ;

		ret += f[v] ;

	}

	for(int i = hea[u] ; i ; i = edge[i].Nxt) {

		int v = edge[i].to ;

		if(v == father) continue ;

		g[v] = (g[u] + ret - f[v] + d[u]) % mod ;

		Dfs2(v , u) ;

	}

}

void query(int u , int father) {

	size[u] = 1 ;

	for(int i = hea[u] ; i ; i = edge[i].Nxt) {

		int v = edge[i].to ;

		if(v == father) continue ;

		query(v , u) ;

		size[u] += size[v] ;

	}

	Ans = (Ans + size[u] * (n - size[u]) * (f[u] + g[u]) + mod) % mod ;

}

# undef int

int main() {

# define int long long

	n = read() ;

	for(int i = 1 , u , v ; i < n ; i ++) {

		u = read() , v = read() ;

		add_edge(u , v) ; add_edge(v , u) ;

		++d[u] ; ++d[v] ;

	}

	Dfs1(1 , 1) ; Dfs2(1 , 1) ; query(1 , 1) ;

    printf("%lld\n",(Ans * inv(n * n)) % mod) ;

    return 0 ;

}

巴特西