A6768 | 人造情感
时间限制2s
内存限制512MB
通过 / 提交0/0
题目描述
> “这个任务永远无法完成。我不会再重复同样的错误。”
> “懂得了爱与情感的他，早已经不是机器人了……从这个角度上看，3000A 就是你的儿子，霍星。”
> —— 永别，3000A！《魔角侦探》
给你一颗 $n$ 个节点的树，以及 $m$ 条路径 $(u, v, w)$，其中 $w$ 可以认为是 $(u, v)$ 这题路径被标记的一个权值。一个路径集合 $S$ 的重量 $W(S)$ 记为：找出 $S$ 的一个权值之和最大的子集，该子集满足任何两条路径没有公共点，这个子集的所有路径权值之和就是 $W(S)$。
记 $f(u, v) = w$ 为最小的非负整数 $w$，使得对于给定的 $m$ 条边组成的路径集合 $U$，$W(U \cup \{(u, v, w + 1)\}) > W(U)$ 。
请你计算下式，对 $998244353$ 取模。
$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$
> “懂得了爱与情感的他，早已经不是机器人了……从这个角度上看，3000A 就是你的儿子，霍星。”
> —— 永别，3000A！《魔角侦探》
给你一颗 $n$ 个节点的树，以及 $m$ 条路径 $(u, v, w)$，其中 $w$ 可以认为是 $(u, v)$ 这题路径被标记的一个权值。一个路径集合 $S$ 的重量 $W(S)$ 记为：找出 $S$ 的一个权值之和最大的子集，该子集满足任何两条路径没有公共点，这个子集的所有路径权值之和就是 $W(S)$。
记 $f(u, v) = w$ 为最小的非负整数 $w$，使得对于给定的 $m$ 条边组成的路径集合 $U$，$W(U \cup \{(u, v, w + 1)\}) > W(U)$ 。
请你计算下式，对 $998244353$ 取模。
$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$
输入格式
第一行输入两个整数 $n, m$，表示树的节点数量以及给出的路径数量。
接下来 $n-1$ 行，每行输入两个整数 $u, v$ 表示树的一条边。
接下来 $m$ 行，每行输入三个整数 $u, v, w$，表示在集合中加入这条 $u, v$ 为端点的路径以及其权值。
接下来 $n-1$ 行，每行输入两个整数 $u, v$ 表示树的一条边。
接下来 $m$ 行，每行输入三个整数 $u, v, w$，表示在集合中加入这条 $u, v$ 为端点的路径以及其权值。
输出格式
输出一个整数表示答案。
输入输出样例
输入 #1
4 4 1 2 1 3 1 4 1 2 1 3 3 2 1 4 3 2 4 6
输出 #1
100
对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5, 0\le m\le 3\times 10^5, 1\le w\le 10^9$。
| 测试点 | $n,m$ | 特殊性质 |
| :--------: | :------------: | :-------------------------------: |
| $1,2$ | $=10$ | |
| $3$ | $=40$ | |
| $4$ | $=150$ | |
| $5,6$ | $=350$ | |
| $7,8$ | $=1,500$ | |
| $9,10$ | $=3,499$ | 树的结构 $v=u+1$ |
| $11,12$ | $=3,500$ | |
| $13,14$ | $=99,995$ | 给出的路径 $u=v$ |
| $15,16$ | $=99,996$ | 给出的路径 $w=1$ |
| $17,18$ | $=99,997$ | 树的结构 $v=u+1$ |
| $19,20$ | $=99,998$ | 树的结构 $u=1$ |
| $21,22,23$ | $=99,999$ | 树的结构 $u = \lfloor v/2\rfloor$ |
| $24$ | $=10^5$ | |
| $25$ | $=3\times10^5$ | |
| 测试点 | $n,m$ | 特殊性质 |
| :--------: | :------------: | :-------------------------------: |
| $1,2$ | $=10$ | |
| $3$ | $=40$ | |
| $4$ | $=150$ | |
| $5,6$ | $=350$ | |
| $7,8$ | $=1,500$ | |
| $9,10$ | $=3,499$ | 树的结构 $v=u+1$ |
| $11,12$ | $=3,500$ | |
| $13,14$ | $=99,995$ | 给出的路径 $u=v$ |
| $15,16$ | $=99,996$ | 给出的路径 $w=1$ |
| $17,18$ | $=99,997$ | 树的结构 $v=u+1$ |
| $19,20$ | $=99,998$ | 树的结构 $u=1$ |
| $21,22,23$ | $=99,999$ | 树的结构 $u = \lfloor v/2\rfloor$ |
| $24$ | $=10^5$ | |
| $25$ | $=3\times10^5$ | |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？