#P6720. [2019山东冬令营]kevinshuai小姐姐的函数式线段树合并维护动态点分治好题
[2019山东冬令营]kevinshuai小姐姐的函数式线段树合并维护动态点分治好题
[2019山东冬令营]kevinshuai小姐姐的函数式线段树合并维护动态点分治好题
题目描述
红魔乡有 座屋子,由 条无向边连接成一棵树。第 座屋子里住着编号为 的妹子。
第 位妹子有两个偏好属性 ,分别表示对较亮、较暗环境的偏好程度。第 条边可以设置为较亮或较暗,两种状态分别具有属性 。
陪第 位妹子经过第 条边时,可以自行选择该边的状态:
- 选择较亮状态,获得 点好感度。
- 选择较暗状态,获得 点好感度。
令 表示陪第 位妹子从屋子 走到屋子 ,沿唯一简单路径能够获得的最大好感度总和。可以在经过每条边时独立选择状态;不同 的状态选择也相互独立。若 ,路径为空,。
求
$$\sum_{x=1}^{n}\sum_{y=1}^{n}F(x,y)\pmod{998244353}.$$输入格式
第一行一个整数 ,表示屋子数量。
接下来 行,每行两个非负整数 ,表示第 位妹子的属性。
接下来 行,每行四个整数 ,表示连接屋子 的一条无向边及该边的两种环境属性。
输出格式
输出一行一个非负整数,表示答案对 取模的结果。
数据范围
所有数据满足 ,,,输入的图为树。
下表各行表示不同部分的数据:
| 数据比例 | 附加限制 |
|---|---|
| 所有 | |
| 每条边的 | |
| 第 条边满足 | |
| ,所有 | |
| 剩余数据 | 无 |