TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5458
  • 题目
  • P5458生成树求和
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s,512m
    问题描述

    给定一张 \(n\) 个点 \(m\) 条边的带权无向图 \(G\),对于 \(G\) 的每一棵生成树,我们定义这棵生成树的权值为:它所包含的所有边的边权按三进制不进位加法相加所得的数。

    现在请你求出图 \(G\) 中所有的生成树的权值和(将生成树的权值由三进制转为十进制,做正常的十进制进位加法)。输出答案对 \(10 ^ 9 + 7\) 取模后的值即可。

    输入格式

    第一行两个整数 \(n, m\) 表示点数与边数。点从 \(1 \sim n\) 编号。

    接下来 \(m\) 行每行三个整数 \(a, b, c\) 表示一条连接 \((a, b)\) 的边权为 \(c\) 的无向边。

    边权以十进制形式给出。

    输出格式

    仅一行一个整数表示答案。

    样例输入

    5 7
    3 2 7400
    4 1 1618
    4 2 9110
    4 3 4264
    5 1 537
    5 2 4240
    5 3 655

    样例输出

    262221

    提示

    \(30 \%\) 的数据(共六个点):\(n = 5, 6, 7, 8, 9, 10\)
    \(50 \%\) 的数据:\(n \le 30\)
    \(70 \%\) 的数据:\(n \le 40\)
    \(100 \%\) 的数据:\(n \le 100, m \le \frac{n(n-1)}{2}, 0 \leq c \leq 10 ^ 4\),保证无重边无自环。


    来源  长乐集训 2017