{"problem":{"name":"「SiR-1」Lighthouse","description":{"content":"给定一棵 $n$ 个点的树，每个点有权值 $w_i$，初始为 $0$。初始得分 $s=0$。 进行 $m$ 次操作，每次操作选择一个点 $u$，给 $s$ 增加 $u$ 所在的同点权连通块的大小（即，假设只保留点权等于 $w_u$ 的点，和连接两个点权等于 $w_u$ 的点的边，对得分的贡献就是此时 $u$ 所在的连通块大小。注意这不会真的删去一部分树上的点和边），然后给 $w_u$ 增加 $1","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9357"},"statements":[{"statement_type":"Markdown","content":"给定一棵 $n$ 个点的树，每个点有权值 $w_i$，初始为 $0$。初始得分 $s=0$。\n\n进行 $m$ 次操作，每次操作选择一个点 $u$，给 $s$ 增加 $u$ 所在的同点权连通块的大小（即，假设只保留点权等于 $w_u$ 的点，和连接两个点权等于 $w_u$ 的点的边，对得分的贡献就是此时 $u$ 所在的连通块大小。注意这不会真的删去一部分树上的点和边），然后给 $w_u$ 增加 $1$。\n\n请对所有 $n^m$ 种操作方式，求它们的得分 $s$ 之和，对 $10^9+7$ 取模。\n\n## Input\n\n第一行两个正整数，表示 $n,m$。\n\n其后 $n-1$ 行每行两个正整数，表示一条边的两个端点 $u,v$。\n\n## Output\n\n输出一个整数，表示结果对 $10^9+7$ 取模后的结果。\n\n[samples]\n\n## Note\n\n对于所有数据，满足 $1\\leq n\\leq 1000$，$1\\leq m\\leq 10^5$，$1\\leq u,v\\leq n$，保证输入是一棵树。\n\n- Subtask 0（5 pts）：$n,m\\le 7$。\n- Subtask 1（20 pts）：$n,m\\le 10$。\n- Subtask 2（15 pts）：$n,m\\le 50$。\n- Subtask 3（15 pts）：$n,m\\le 100$。\n- Subtask 4（15 pts）：$n\\le 50$。\n- Subtask 5（15 pts）：树是一条链。\n- Subtask 6（15 pts）：无特殊限制。\n\n本题同时开启子任务依赖。具体地：\n\n+ 对于子任务 $i(i \\in [1, 3])$，依赖于子任务 $0 \\sim (i -  1)$；\n+ 对于子任务 $4$，依赖于子任务 $0 \\sim 2$；\n+ 对于子任务 $6$，依赖于子任务 $0 \\sim 5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9357","tags":["数学","递推","洛谷原创","O2优化","组合数学","洛谷月赛"],"sample_group":[["3 2\n1 3\n2 3","40"]],"created_at":"2026-03-03 11:09:25"}}