zcmimi's blog

categories/刷题记录/共659篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

dfs序作为下标,深度作为时间轴

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

动态开点线段树模板

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

模板

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

Count-on-a-tree-II top: 0

树上莫队模板

avatar
zc
2020-01-18 21:03:00
查看原题

点击跳转

[国家集训队]happiness有点像

而且建图更加简化了

答案为总和减去最小割

(i+j)\&1,(i',j')(i,j)相邻,黑白染色建图

st\xrightarrow{A} (i,j)\xrightarrow{B}ed

st\xrightarrow{B} (i',j')\xrightarrow{A}ed

(i,j) \xleftrightarrow{c_{i,j}+c_{i',j'}} (i',j')

ABBAc[i][j]+c[i'][j']c[i][j]+c[i'][j']sti,ji',j'ed

假设(i,j)选择A,那么要断开(i,j)\rightarrow t,(i,j)\rightarrow (i',j')

这些边上的权值会从答案中减去

最小割可以最小化要减去的权值,所以答案最大

avatar
zc
2020-01-06 01:03:00
查看原题

点击跳转

先考虑没有换根的操作(设根节点为1)

修改点x的权值

被影响的只有1\rightarrow x上的点,设p_1,p_2,...,p_k1\rightarrow x上的点

s_ii子树点权和

将修改看成增加v

修改后贡献为

\sum_{i=1}^k (s_{p_i}+v)^2-\sum_{i=1}^k s_{p_i}^2= k\times v^2+2v\sum_{i=1}^ks_{p_i}

我们需要预处理出s_i^2,维护s_i

考虑换根操作:

x为根,p_1,p_2,...,p_k1\rightarrow x上的点

a_i为在1为根时v_i的点权和,b_i为在x为根时v_i的点权和

可以发现a_{i+1}+b_i=a_1=b_k(因为所有点的点权和总是相同)

ans_x表示x为根时的答案

ans_x=ans_1+\sum_{i=1}^k b_i^2-a_i^2

=ans_1+\sum_{i=1}^k (a_1-a_{i+1})^2-a_i^2

=ans_1+\sum_{i=2}^k (a_1-a_i)^2-a_i^2

=ans_1+ (k-1)a_1^2- 2a_1\sum_{i=2}^k a_i

=ans_1+ s_1[(k+1)s_1-2\sum_{i=1}^k s_{p_i}]

可以使用树链剖分+(树状数组/线段树)或LCT维护

avatar
zc
2020-01-05 18:45:00
查看原题

点击跳转

换根树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

情况1: x就是根,直接输出整棵树的和

情况2: 根在x子树内:

找到根到x路径上的x的儿子

avatar
zc
2020-01-05 12:24:00
查看原题

点击跳转

考虑一种颜色对答案的贡献

把树中这种颜色的点都删掉,那么就会有很多的小树,这些小树中的点互相之间不会产生贡献,而不同树的两个点之间会产生贡献。

可以得到每一种颜色,点的sum值就是n - 所在小树的size

一个点的sum就是n * 颜色数 - 每种颜色节点所在小树的size

avatar
zc
2020-01-04 20:29:00
查看原题

点击跳转

点分治

29/66
Search
search