自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:15:39，当前版本为作者最后更新于2025-05-20 11:46:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

学生模拟赛 T3 怒砍 $13$ 分，润过来随便做一点简单题。

你能在 $5$ 分中之内完成这道题的题意理解与编码吗？

这题的意思就是，在边上染 $m$ 种颜色，问有多少个极大的同色连通块。

一个连通块可以找一个代表元。比如我们找这个联通块的 LCA 上连的编号最小的边。那这条边只需要满足：

1. 所有编号比他小但是父亲相同的边都和他不同色；
2. 这条边的父亲（指的是连接的父亲节点）要么不存在，要么和它不同色。

假设有 $e$ 条边有限制，那么答案就是 $(1-\frac{1}{m})^e$。

直接做就完了，虽然可以推式子做到连 DFS 都不需要，但是我不想再往后走了。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e6+10,MOD=1e9+7;
int n,m,ans,inv;
vector<int> G[MAXN];
int qpow(int base,int p) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
void dfs(int u,int f) {
	int al=!!f;
	for(auto v:G[u]) if(v!=f) ans=(ans+qpow(1-inv,al))%MOD,dfs(v,u),al++;
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,inv=qpow(m,MOD-2);
	ffor(i,1,n-1) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
	dfs(1,0);
	cout<<(ans%MOD+MOD)%MOD;
	return 0;
}