CF1797F 题解

· · 题解

吐槽：打这场 \texttt{CF} 的时候就觉得 F 不难，然后还是花了一些时间才做出来。这是 \texttt{CN} 场，于是 E,F 都非常套路，基本上是见过套路会做没见过不会做，希望出题人可以多考察思维。

首先要想到的是肯定是在原来的答案上计算修改后增加的贡献。

容易想到容斥，令 A 表示 (u,v),u<v 满足 u 是 u\to v 路径上编号最小的点构成的集合，B 表示 (u,v),u<v 满足 v 是 u\to v 路径上编号最大的点构成的集合。则答案为 |A|+|B|-2|A\cap B| 。

我们先思考修改为造成什么贡献。令修改为 (i,x),i>n 。对 B 的影响显然是增加 i-1。考虑对 A 的影响，令修改后的集合为 A'。若 (u,x)\in A，则显然有 (u,i)\in A，显然也有 (i,x)\in A'，其他 (t,i) 都 \not\in A'。

我们令 c_v 表示 u 的个数满足 \forall\ k 在 u\to v 的路径上，u\le k。

则我们对于修改有 c_i=c_x+1。

容易推得 |A\cap B| 的增加量和 |A| 的是一样样的。于是修改的影响为：c_i\gets c_x+1,ans\gets ans+i-1-c_i。

下面只要计算最初的 ans 和 c_i 即可。

前置知识：点权多叉重构树，不会的可以到魏老师的博客学习。

记 x,y 在重构树上的 \text{lca} 为原树上的路径 x \to y 上的最大、小值构成的树分别为 T_1,T_2。

则最初的 c_i 为 i 在 T_2 上的深度 -1，若 (u,v)\in A\cap B，则 x 在 T_1 上是 y 的祖先，y 在 T_2 上是 x 的祖先。

即在 T_2 上 y 在 x 到根的路径上，在 T_1 上 dfn_x\in[dfn_y,dfn_y+sz_y)。\texttt{dfs}+ 树状数组计数即可。

void dfs1(int x,int f)
{
    ans-=2*(B.ask(mx.id[x]+mx.siz[x]-1)-B.ask(mx.id[x]-1));B.add(mx.id[x],1);
    for(int i=mn.e.head[x];i;i=mn.e.e[i].nex)
    {
        int to=mn.e.e[i].to;
        if(to!=f) dfs1(to,x);
    }B.add(mx.id[x],-1);
}

完整代码看这里。