B-小y的树_牛客练习赛96

题目大意：

​ 一颗高度为n的k叉树，求任意两点的距离和。

思路和代码：

牛客的题还是难啊

以三层三叉树为例

先算出根节点到其他所有节点的距离和。（上图红色）

首先要注意，同一层的节点到其他所有点的距离和是相同的。我们只要算出每一层的权值即可。如上图，我们从第一次移到第二层时，黄色部分的所有节点距离减一，红色部分所有节点距离加一。

inline ll qp(ll a, ll k, ll p) {
	ll res = 1;//快速幂
	a %= p;
	while (k) {
		if (k & 1) res = res * a % p;
		a = a * a % p;
		k >>= 1;
	}
	return res;
}
 
inline ll inv(ll x,ll p){//逆元
	return qp(x,p-2,p);
}

void solve(){
	
	cin >> n >> k ;
	
	vct<ll> p(n + 1 , 0) ;// 高度为i的树的节点数量 
	vct<ll> num(n + 1 , 0) ;// 该层权值 
	p[1] = 1 ;
	rep(i , 2 , n) p[i] = (p[i - 1] + qp(k , i - 1 , mod) % mod) % mod ;
	
	rep(i , 1 , n - 1) num[1] = (num[1] + i * qp(k , i , mod) % mod) % mod ;
	
	ll ans = num[1] ;
	rep(i , 2 , n){
		num[i] = ((num[i - 1] - 2 * p[n - i + 1] % mod + mod) % mod + p[n] % mod) % mod ;
		ans = (ans + qp(k , i - 1 , mod) * num[i] % mod) % mod ;
	}
	show1(num , 1 , n) ; 
	ans = (ans * inv(2 , mod)) % mod ;
	cout << ans ;
	
}//code_by_tyrii 

小结：

这道题需要抓住每一层权值相同的关系