跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0312. #6271. 「长乐集训 2017 Day10」生成树求和 加强版

  • ID: 318
  • 传统题
  • 2000ms
  • 512MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 图论
  • 组合数学
  • 数学
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#6271. 「长乐集训 2017 Day10」生成树求和 加强版

题目描述

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

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

输入格式

第一行两个整数 表示点数与边数。点从 编号。

接下来 行每行三个整数 表示一条连接 的边权为 的无向边。

边权以十进制形式给出。

输出格式

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

样例

样例输入

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

样例输出

262221

数据范围与提示

的数据(共六个点):
的数据:
的数据:
的数据:,保证无重边无自环。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 216 题。保留原作者与原赛事署名。