zcmimi's blog
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
查看原题

点击跳转

点分治

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

点击跳转

点分治

avatar
zc
2020-01-04 10:21:00
查看原题

点击跳转

我们先预处理出L_i,R_i分别表示与a_i相同的数出现在i左边和右边的位置

我们可以使用分治来判断一个区间是否合法

我们设当前区间为[l,r]

从两边一起找

假设枚举到位置iL_i<lR_i>r,那么左端点在[l,i],右端点在[i,r]的区间都是"non-boring"

这时我们只需要判断区间[l,i-1][i+1,r]是否合法就可以了

复杂度可以降至\Theta(n \log n)

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

点击跳转

avatar
zc
2020-01-01 17:27:00
查看原题

点击跳转

qwq

qwq

> > > qwq

avatar
zc
2019-12-31 22:54:00
查看原题

点击跳转

夫妻之间:girl \to boy

情人之间:boy \to girl

Tarjan求强连通分量,对于一对夫妻,如果两人在同一个强连通分量里,那么这对婚姻就是不安全的,反之,则是安全的。

avatar
zc
2019-12-31 21:29:00
查看原题

点击跳转

假设当前被封锁的是x

如果x不是割点,那么除x外的点都连通,答案为2\times(n-1)(x和其他n-1个点配对)

如果x是割点,删掉x后图会变成若干个连通块,设这些连通块大小为t_1,t_2,...,t_a

那么答案为:\sum_{i=1}^a t_i\times(n-t_i)+(1+sum)\times(n-sum-1)+n-1

avatar
zc
2019-12-31 20:01:00
查看原题

点击跳转

分类讨论:

Tarjan跑出割点,然后DFS搜索所有的联通快

计算每一个联通快中的割点数目

分类讨论:

  1. 没有割点

    至少需要建立两个出口

    从任意非割点的地方选择两个点建立

  2. 这个分组只有一个割点

    只需要在分组内设立一个出口

    可以设立在任意一个非割点的地方

  3. 有两个及以上个割点,则无需建立,可以直接到达其他联通块

36/73
Search
search