「CodeVS 1391」伊吹萃香 - 分层图最短路

今天校内模拟赛的最后一题

没想到竟然很水

然后就 AK 了(逃

给定一个图

n个黑白点,m条有向边

每个节点初始有一个质量weight[i]

走过每一条边需要消耗一定量的体力以及1个单位的时间

由于黑白点的存在,走过每条路需要消耗的体力也就产生了变化,假设一条道路两端路口黑白洞的质量差为delta:

  1. 从白到黑,消耗的体力值减少delta,若该条路径消耗的体力值变为负数的话,取为0

  2. 从黑到白,消耗的体力值增加delta

  3. 同色,消耗的体力值无变化

每过1个单位时间,就把每个点的黑白颜色相反

可以选择在一个点上停留1个单位的时间,如果是白点,则不消耗体力,否则消耗cost[i]的体力

1 <= N <= 5e3

1 <= M <= 3e4

「Codeforces 739B」Alyona and a tree - 倍增 + 差分

给定一棵节点数为`n`的树

这棵树的根节点为`1`

这棵树有点权`val_i`和边权`dis_i`

定义`dist(u,v)`为从`u`到`v`的简单路径上的边权和

顶点`u`控制顶点`v`,当且仅当`v`在`u`的子树中且`dist(u,v) \le val_v`

求每个顶点`u`能控制几个顶点

`1 \le n \le 2 \times 10^5`


:D 一言句子获取中...