arrow_backlca共25篇文章

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

例题: LG 2495 [SDOI2011]消耗战

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

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

我们可以每次都把提供

查看原题

点击加载点击跳转

查看原题

点击加载点击跳转

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

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

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

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

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

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

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

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

详细见代码

查看原题

点击加载点击跳转

链上的情况

情况一

记录每个点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_i为i的祖先中颜色与i相同的深度最大的点

第一问

设x与y中x离\texttt{lca}(x,y)更近

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

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

第二问

设A与B中A离\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})

查看原题

点击加载点击跳转

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

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

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

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

看上去不是很好处理

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

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

详见代码

查看原题

点击加载点击跳转

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

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

查看原题

点击加载点击跳转

可以看出这是多颗基环树

分三种情况:

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

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

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

查看原题

点击加载点击跳转

线性基搬到了树上

线性基是支持合并的

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

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

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

查看原题

点击加载点击跳转

交互题

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

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

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

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

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

查看原题

点击加载点击跳转

可以发现有三种路径:

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)