题解：P12450 [INOI Team Selection 2021] Maximal Tree Coloring

· · 题解

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;
}