zcmimi's blog

arrow_backlca共24篇文章

avatar
zcmimi
2020-09-25 14:51:21

虚树是一种统计树上信息的技术

例题: LG 2495 [SDOI2011]消耗战

如果树的点数很少,可以直接树上dp

可以发现\sum k_i \le 5 \times 10^5

我们可以每次都把提供

avatar
zc
2020-10-15 22:15:41

查看原题

点击跳转

首先可以用并查集判断每个1操作是否有效

接下来很容易可以想到树剖+线段树优化建图

很可惜,出题人卡了这种大常数做法

考虑直接在树上倍增优化建图

和倍增lca差不多,一直向上连边

而每个点又拆为入点和出点

每次构建传送门时新建一个点,

连边时只需要[u_1,v_1]所在的块出点连接新建点,新建点连接[u_2,v_2]所在的块入点

详细见代码

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

点击跳转

链上的情况

情况一

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树统计即可

情况二

考虑每个点对答案的贡献,分类讨论

  1. i\in [1,A]

    那么满足的y\in (pre_i,i],x\in [i,A]

    x\in (pre_i,i],y\in [i,B]

    总贡献为\sum (i-pre_i)\times(A+B-2i+2)-1

    (-1为了避免[i,i]被重复计算)

    拆下式子: (A+B+2)(\sum i-pre_i)-2(\sum i(i-pre_i))-\sum 1

    可以发现这种情况可以直接前缀和维护

  2. i\in (A,B],满足pre_i<A

    那么满足的x\in (pre_i,A],y\in [i,B]

    总贡献为\sum (A-pre_i)\times(B-i+1)

    拆下式子(A\sum 1-\sum pre_i)(B+1)-A\sum i+\sum ipre_i

    可以发现这种情况可以用主席树维护

树上情况

观察数据形成方式:

  • p个点形成一条主链,其他点随机向主链连边
    所以树上任意点对的\texttt{lca}距离他们期望为\mathcal O(\log n)
  • 每个点的颜色在[1,n]中随机,每种颜色数目期望为1

pre_ii的祖先中颜色与i相同的深度最大的点

第一问

xyx\texttt{lca}(x,y)更近

首先求出y\texttt{lca}链上的颜色总数,

然后再暴力枚举x\texttt{lca}链上的颜色更新答案

第二问

ABA\texttt{lca}(A,B)更近

分类讨论:

  1. x\in [1,\texttt{lca}],y\in [1,B],与链上的情况相同
  2. x\in [\texttt{lca},A],y\in [1,\texttt{lca}]

    x\in [1,A],y\in [1,\texttt{lca}]的答案减去

    x,y\in [1,\texttt{lca})的答案\sum (2(i-pre_i)(\texttt{lca}-i)-1)

    拆下式子: 2\texttt{lca}\sum (i-pre_i) - 2\sum i(i-pre_i)-\sum 1

  3. x\in [\texttt{lca},A],y\in [\texttt{lca},B]

    先求出i\in [\texttt{lca,B}]的贡献\sum (B-i+1)(A-\texttt{lca}+1)

    拆下式子: (A-\texttt{lca}+1)(\sum B+1 - \sum i)

    然后用i\in (\texttt{lca},A]更新

    pre_i\le\texttt{lca},设j[\texttt{lca},B]中第一个与它颜色相同的点

    贡献: (A-i+1)(j-\texttt{lca})

avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

题意: 给一颗树,每条边权值可以修改为x,使得修改后这条边可以在最小生成树上,问x最大可以是多少?

首先求出最小生成树(以下的树指最小生成树)

修改一条边时,若不是最小生成树上的边,则为树上该边两端节点之间的最大值

若是树上的边,那么就是该边子树中找出一些非树边(使它们最大值尽可能小)连接除子树部分的点,答案为该边权值

看上去不是很好处理

我们将非树边按权值从小到大排序,从下往上合并,用并查集维护即可

每次遇到非树边x,y时,就更新并合并x\to \text{lca}_{x,y},y\to \text{lca}_{x,y},从下往上跳时,并查集可以跳过已经打过标记的边

详见代码

avatar
zc
2020-09-10 14:05:00
查看原题

点击跳转

每次给一个叶子节点添加两个儿子,而这个叶子节点能到达的最远的点,也就是上一次求得的直径的两个端点之一

那么每添加一个点更新改点,比较直径与该点到之前直径两端的距离即可

avatar
zc
2020-06-14 13:07:00
查看原题

点击跳转

可以看出这是多颗基环树

分三种情况:

  1. x,y在不同的两颗树上

  2. x,y还没到达环就相遇了

  3. x,y的祖先在环上不同位置

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

点击跳转

线性基搬到了树上

线性基是支持合并的

这题就是倍增暴力合并线性基

虽然O(\log^3_2n)的复杂度已经可以通过了,但是还有更优的方法

在倍增找出询问两点的lca,然后以rmq的方式合并+查询线性基,可以将复杂度降到O(\log^2_2n)

avatar
zc
2020-05-03 11:51:00
查看原题

点击跳转

交互题

我们从叶子节点开始搜索,把所有叶子节点添加到队列中

每次从队列中弹出两个叶子节点,

如果lca为其中一个,那么这个lca就是树根

否则删除这两个节点,可能会形成新的叶子节点,加入队列

因为最坏情况下每次都会删掉两个节点,那么重复\frac n2次后,也就只剩下根节点了

avatar
zc
2020-05-03 11:09:00
查看原题

点击跳转

可以发现有三种路径:

  1. a \leftrightarrow b

  2. a \leftrightarrow x \leftrightarrow y \leftrightarrow b

  3. a \leftrightarrow y \leftrightarrow x \leftrightarrow b

只需要判断这三条路径是否满足就可以了

可以发现只要dis\le k而且和k同奇偶就是符合的

(比如x\leftrightarrow y可以一直循环,变成x\leftrightarrow y \leftrightarrow x \leftrightarrow y \dots,每次长度+2)

avatar
zc
2020-04-12 15:41:00
查看原题

点击跳转

1 x表示把点x到根节点的路径上所有的点染上一种没有用过的新颜色

从这里可以看出每种颜色在树上都是一条链的形式存在

可以发现这和LCT很像

那么1操作可以看成access操作,(如何操作先放着

x到根的颜色种数也就是要经过的虚边的条数,设为S_x

xy的路径的权值,可以使用树上差分的形式

也就是转化为S_x + S_y - 2\times S_{lca(x,y)} + 1

3操作也就是求子树最值

我们回过头来看access操作:

  1. 原来的实边变虚,意味着要多走一条虚边,将此链所管辖的区域全部+1

  2. 虚边变实边,意味着要多少一条虚边,将此链所管辖的区域全部-1

注意: LCTsplay的父子关系并不是原树中的父子关系,要找到该splay中深度最小的节点(也就是这条链的顶端再操作)

综上可以用 lct+lca+dfs序+线段树 解决

当然也可以通过树剖模拟access的形式来解决

1/3
Search
search