package main import ( "bufio" "fmt" "os" ) func main() { yuki1451() } func yuki1451() { // https://yukicoder.me/problems/no/1451 // 初始时有n个人 // 给定m个操作,每次将i和j所在的班级合并,大小相等时随机选取班长,否则选取较大的班级的班长作为新班级的班长 // 对每个人,问最后成为班长的概率 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() const MOD int = 1e9 + 7 pow := func(base, exp, mod int) int { base %= mod res := 1 % mod for ; exp > 0; exp >>= 1 { if exp&1 == 1 { res = res * base % mod } base = base * base % mod } return res } var INV2 = pow(2, MOD-2, MOD) var n, m int fmt.Fscan(in, &n, &m) edges := make([]Edge, 0, m) for i := 0; i < m; i++ { var u, v int fmt.Fscan(in, &u, &v) u, v = u-1, v-1 edges = append(edges, Edge{u, v, 1}) } forest, roots, _ := KruskalTree(n, edges) subSize := make([]int, len(forest)) var getSubSize func(int) int getSubSize = func(cur int) int { if cur < n { // 原始顶点 subSize[cur] = 1 } for _, to := range forest[cur] { subSize[cur] += getSubSize(to) } return subSize[cur] } for _, root := range roots { getSubSize(root) } res := make([]int, n) var run func(int, int) run = func(cur, p int) { if cur < n { // 原始顶点 res[cur] = p return } if len(forest[cur]) == 1 { // 只有一个子节点 run(forest[cur][0], p) return } left, right := forest[cur][0], forest[cur][1] // 两个子节点 if subSize[left] > subSize[right] { run(left, p) } else if subSize[left] < subSize[right] { run(right, p) } else { run(left, p*INV2%MOD) run(right, p*INV2%MOD) } } for _, root := range roots { run(root, 1) } for _, v := range res { fmt.Fprintln(out, v) } } type Edge struct{ from, to, weight int } // 表示合并过程的树,按照edges中边的顺序合并顶点. // // 返回: // forest: 森林的有向图邻接表 // roots: 新图中的各个根节点 // values: 每个辅助结点的权值(即对应边的权值,叶子结点权值为0). func KruskalTree(n int, edges []Edge) (forest [][]int, roots []int, values []int) { parent := make([]int32, 2*n-1) for i := range parent { parent[i] = int32(i) } forest = make([][]int, 2*n-1) values = make([]int, 2*n-1) uf := NewUf(n) aux := int32(n) for i := range edges { e := &edges[i] from, to := int32(e.from), int32(e.to) f := func(big, small int32) { w, p1, p2 := e.weight, int(parent[big]), int(parent[small]) forest[aux] = append(forest[aux], p1) forest[aux] = append(forest[aux], p2) parent[p1], parent[p2] = aux, aux parent[big], parent[small] = aux, aux values[aux] = w aux++ } uf.Union(from, to, f) } forest = forest[:aux] values = values[:aux] for i := int32(0); i < aux; i++ { if parent[i] == i { roots = append(roots, int(i)) } } return } type Uf struct { data []int32 } func NewUf(n int) *Uf { data := make([]int32, n) for i := 0; i < n; i++ { data[i] = -1 } return &Uf{data: data} } func (ufa *Uf) Union(key1, key2 int32, f func(big, small int32)) bool { root1, root2 := ufa.Find(key1), ufa.Find(key2) if root1 == root2 { return false } if ufa.data[root1] > ufa.data[root2] { root1, root2 = root2, root1 } ufa.data[root1] += ufa.data[root2] ufa.data[root2] = int32(root1) f(root1, root2) return true } func (ufa *Uf) Find(key int32) int32 { if ufa.data[key] < 0 { return key } ufa.data[key] = ufa.Find(ufa.data[key]) return ufa.data[key] } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a > b { return b } return a }