Li Hua and Path题解

· · 个人记录

Li Hua and Path

令集合 A 表示满足第一种路径的 (u,v) 集合

集合 B 表示满足第二种路径的 (u,v) 集合

集合 C 表示满足两种路径的 (u,v) 集合

那么答案就是 |A|+|B|-2|C|

集合 |A|,|B| 很好计算，考虑如何计算出原始的 |C|

考虑建出大根小根的点权重构树：

以大根为例，具体的构建方法为：从小到大枚举每个节点，考虑节点在原树上连向的其他节点，如果其他节点编号小于该节点，那么将其他节点所在子树的根连向该节点，并以该节点为父亲。

考虑点权重构树的性质（以大根为例）：父亲的点权必然会大于儿子的点权，对于原树中 (u,v) 的路径中经过最大的点就是在大根树中 u,v 的 LCA。

同样对于小根来说，对于原树中 (u,v) 的路径中经过最小的点就是在小根树中 u,v 的 LCA。

所以我们就可以在小根重构树中枚举每个点 u，看 u 在以 u 为大根树子树中有多少个点 v 满足在小根树中 v 是 u 的祖先，那么 (u,v) 就是满足 C 条件

那么我们考虑新加入的点 k，它的父亲是 x，考虑他对每一个集合的贡献，显然他对 A 的贡献就是他在小根树中的深度，而对 B 的贡献就是树的节点个数，对 C 的贡献同样是在小根树的深度，而根据定义，在小根树的深度恰好 x 的深度 +1

上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+50;
int n,m,ans,dfc;
int dep[N],fa[N],sz[N],st[N],ed[N];
int tr[N];
vector<int> mx[N],mn[N],e[N];
int lb(int x) {return x & -x;}
void add(int wz,int x) {while(wz<=n) tr[wz]+=x,wz+=lb(wz);}
int query(int wz) {int re=0;while(wz) re+=tr[wz],wz-=lb(wz);return re;}
int find(int u) {if(u!=fa[u]) return fa[u]=find(fa[u]);else return u;}
void merge(int u,int v)
{
    u=find(u),v=find(v);
    if(u==v) return ;
    fa[v]=u;
}
void dfs1(int u)
{
    sz[u]=1;
    st[u]=++dfc;
    for(int v:mx[u]) dfs1(v),sz[u]+=sz[v];
    ans+=sz[u]-1;
    ed[u]=dfc;
}
void dfs2(int u)
{
    sz[u]=1;
    for(int v:mn[u]) dep[v]=dep[u]+1,dfs2(v),sz[u]+=sz[v];
    ans+=sz[u]-1;
}
void dfs3(int u)
{
    ans-=2*(query(ed[u])-query(st[u]-1));
    add(st[u],1);
    for(int v:mn[u]) dfs3(v);
    add(st[u],-1);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1,u,v;i<n;i++) scanf("%lld %lld",&u,&v),e[u].push_back(v),e[v].push_back(u);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int u=1;u<=n;u++)
        for(int v:e[u]) if(v<u&&find(u)!=find(v))
            mx[u].push_back(find(v)),merge(u,v);
    for(int i=1;i<=n;i++) fa[i]=i;
    dfs1(n);
    for(int u=n;u>=1;u--)
        for(int v:e[u]) if(v>u&&find(u)!=find(v))
            mn[u].push_back(find(v)),merge(u,v);
    dfs2(1);
    dfs3(1);
    printf("%lld\n",ans);
    scanf("%lld",&m);
    for(int i=1,u;i<=m;i++)
    {
        scanf("%lld",&u);
        dep[n+i]=dep[u]+1;
        ans+=n+i-dep[n+i]-1;
        printf("%lld\n",ans);
    }
    return 0;
}