在神秘的大清,有更多的ddl,就会有更多咕咕咕的方法。

准确的说,ddl是一棵大小为 

n

 的树,第一个节点是网络科学,第二个节点是博弈论…

Lyra 的暑期计划(除了陪 Evan 之外)是一个每个元素在 

[1,n]

 的序列,她计划完成一个长度为偶数的子区间的ddl,并且咕咕咕掉剩下的。

她会给区间内的ddl两两配对,两个ddl如果很接近,那么她就只需要把第一个ddl要交的作业稍作修改,在网络学堂上上传到第二个ddl。

Lyra 很聪明,所以她总是能巧妙的把区间内的ddl两两匹配使得匹配的ddl之间在树上的距离之和(唯一简单路上的边权和)最小。每个长度为偶数的区间的完成时间定义为最小配对方法中每对匹配点间距离的总和。

作为 Lyra 的朋友,你要帮她求序列每个长度为偶数的区间的ddl的完成时间之和。

输入格式

第一行两个整数 

n,m

 表示树的大小和序列的长度。

接下来 

n1

 行每行三个整数 

u,v,w

 表示一条连接 

u,v

 长度为 

w

 的树边。

接下来一行 

m

 个整数表示序列。

注意:本题输入可能很大,建议采用较为快速的读入方式。

输出格式

一行一个整数表示答案,由于答案可能很大,输出其对 

998244353

 取模的结果。

样例一

input

output

explanation

一共只有 

4

 个区间需要计算,点集分别为 

{2,3},{3,1},{1,4},{2,3,1,4}

, 最小完成时间分别为 

2,3,4,2

,于是总和为 

11

样例二

input

output

样例三

见样例数据下载。

限制与约定

本题采用捆绑测试,只有通过一个子任务的全部测试点才可以得到子任务的得分。

对于全部数据 

1n,m105;1w109.

 

子任务 分值

n

的规模

m

的规模

特殊限制
1 5

100

 

100

 

2 15

1000

 

1000

 

3 15

105

 

100

 

4 15

1000

 

105

 

5 15

105

 

n=m

 且序列为一个 

1n

 的排列

6 15 树的生成方式是随机一条边若不形成环则加入,形成树为止
7 20

时间限制

1s

 

空间限制

512MB

首先考虑一条边受到的影响 考虑dp  我们会枚举我的子树里有几个点等待配对 但如果这个点数超过1 那么显然是不优的 所以我们只考虑子树内有1的情况 那么我们再次把子树对应的dll 在序列上标出来 子树内的标记1 其他为0 统计我子树内的0,1序列中有多少个偶数区间和是奇数即可我们接着观察,对于一个确定的ddl区间,一条树边被匹配包含了当且仅当把它删去后树被分成两个包含奇数个ddl的块。若我们令  为根做dfs,则一个非根点父向边被包含当且仅当其子树内有奇数个ddl,因为这个信息我们可以o(1)维护所以我们选择用线段树为该信息 那么我们在每个节点的时候把这个节点的信息添加进去 然后线段树合并上去 每次合并之后 最后算合并完成之后我对父边的贡献即可 具体可以在线段树上维护4个信息  v[0][0/1] v[1][0/1]分别表示下标是奇数/偶数情况下 我标记0,1之后前缀和在奇数/偶数的位置 是奇数/偶数的个数 注意每次插入都需要用update维护 这个值

 

分类: 线段树

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论