#P6720. [2019山东冬令营]kevinshuai小姐姐的函数式线段树合并维护动态点分治好题

    ID: 6570 传统题 1500ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>数据结构树状数组CF2300树形DP数学线段树可持久化分治

[2019山东冬令营]kevinshuai小姐姐的函数式线段树合并维护动态点分治好题

[2019山东冬令营]kevinshuai小姐姐的函数式线段树合并维护动态点分治好题

题目描述

红魔乡有 nn 座屋子,由 n−1n-1 条无向边连接成一棵树。第 ii 座屋子里住着编号为 ii 的妹子。

第 ii 位妹子有两个偏好属性 Ai,BiA_i,B_i,分别表示对较亮、较暗环境的偏好程度。第 jj 条边可以设置为较亮或较暗,两种状态分别具有属性 Cj,DjC_j,D_j。

陪第 ii 位妹子经过第 jj 条边时,可以自行选择该边的状态:

  • 选择较亮状态,获得 Ai+CjA_i+C_j 点好感度。
  • 选择较暗状态,获得 Bi+DjB_i+D_j 点好感度。

令 F(x,y)F(x,y) 表示陪第 xx 位妹子从屋子 xx 走到屋子 yy,沿唯一简单路径能够获得的最大好感度总和。可以在经过每条边时独立选择状态;不同 (x,y)(x,y) 的状态选择也相互独立。若 x=yx=y,路径为空,F(x,x)=0F(x,x)=0。

求

$$\sum_{x=1}^{n}\sum_{y=1}^{n}F(x,y)\pmod{998244353}.$$

输入格式

第一行一个整数 nn,表示屋子数量。

接下来 nn 行,每行两个非负整数 Ai,BiA_i,B_i,表示第 ii 位妹子的属性。

接下来 n−1n-1 行,每行四个整数 ui,vi,Ci,Diu_i,v_i,C_i,D_i,表示连接屋子 ui,viu_i,v_i 的一条无向边及该边的两种环境属性。

输出格式

输出一行一个非负整数,表示答案对 998244353998244353 取模的结果。

数据范围

所有数据满足 1≤n≤5×1051\le n\le5\times10^5,1≤ui,vi≤n1\le u_i,v_i\le n,0≤Ai,Bi,Ci,Di≤5×1050\le A_i,B_i,C_i,D_i\le5\times10^5,输入的图为树。

下表各行表示不同部分的数据:

数据比例 附加限制
10%10\% n≤2000n\le2000
所有 Ai=Bi=0A_i=B_i=0
20%20\% 每条边的 ui=1u_i=1
第 ii 条边满足 ui=i, vi=i+1u_i=i,\ v_i=i+1
n≤105n\le10^5,所有 Ai,Bi,Ci,Di≤105A_i,B_i,C_i,D_i\le10^5
剩余数据 无

原题面 PDF