Bad ass BoBo

Bobo’s big success

Codeforces Round #864 (Div. 2)

D. Li Hua and Tree

题目大意

李华有一棵$n$个节点的有根树，根节点为$1$，第$i$个节点有点权$a_i$
定义一个非叶子节点的重儿子为其所有儿子里子树大小最大的，若有多个大小相同的则取编号最小的
维护$m$次操作
操作一：求以$x$为根的子树的点权和
操作二：记$x$的父亲为$fa_x$，重儿子为$hs_x$，切断$(x, fa_x)$之间的边，新加一条$(hs_x, fa_x)$之间的边
操作二不保证$x$是叶子节点，若$x$是叶子，就忽略该操作

With Bobo

组合游戏概念

$1$.两个玩家
$2$.一个状态集合
$3$.游戏规则是指明玩家在一个状态下可以移动到哪些其他状态
$4$.玩家轮流进行移动
$5$.若当前处于某个状态，玩家根据规则无法移动，则游戏结束
$6$.游戏会在有限步以内结束(有向无环$DAG$)

$P$态和$N$态

$P$态：走到这个状态的玩家赢的状态
$N$态：从这个状态走的玩家赢的状态
至少能走到一个$P$态的状态是$N$态
只能走到$N$态的状态是$P$态
正常规则：终态是$P$态(无法走的人输)
反常规则：终态是$N$态(无法走的人赢)

Codeforces Round #849 (Div. 4)

E. Negatives and Positives

题目大意

给定一个长度为$n$的数组$a$，问经历任意次下列操作后，数组中所有数之和的最大可能值是多少
每次操作可选定一个$i,1\leq i\leq n-1$，使得$a_i=-a_i,a_{i+1}=-a_{i+1}$