hihocoder1954 : 压缩树

传送门

首先求出缩一个点 $x$ 的贡献，就是缩 $x$ 的父亲的贡献加上 $x$ 的子树多减少的深度

假设此时缩父亲的贡献已经考虑过了，那么 $x$ 的子树多减少的深度就是子树的节点数

注意此时要满足 $x$ 不是根节点或根节点的儿子，不然缩和没缩是一样的

设这个贡献为 $sum[x]$

然后把所有操作 $l,r,v$ 离线，遇到一个操作左端点就把 $v$ 插入 $set$，遇到右端点再取出，在过程中动态维护总贡献

考虑把每个当前加入的节点搞一个虚树

对于一次缩节点的操作，如果它不在虚树链上，只会影响 $x$ 与虚树的第一个交点的一条链，更上面的已经缩过了

设交点为 $u$，那么贡献就是 $sum[x]-sum[u]$

如果原本已经在虚树链上了，那么 $x$ 不会有贡献

现在问题是如何求与虚树的交点，考虑原本构造虚树的过程，把节点按 $dfn$ 排序，然后根据与前后节点的 $lca$ 确定具体连边

设前后节点为 $u,v$，如果 $LCA(u,x)=u$ 且 $LCA(v,x)=x$ 那么 $x$ 在虚树边 $(u,v)$ 上，不产生贡献

如果 $LCA(u,x)!=u$ 且 $LCA(v,x)=x$ 那么 $x$ 还是在虚树上 $v$ 到根的路径上，不产生贡献

如果 $LCA(u,x)=u$ 且 $LCA(v,x)!=x$ ，或者 $LCA(u,x)!=u$ 且 $LCA(v,x)!=x$ 那么说明 $x$ 有多出来一段不在虚树还没统计的贡献

显然多出来的一段是 $LCA(u,x),LCA(v,x)$ 中深度较大的节点 $p$ 与 $x$ 的一条链的贡献，贡献为 $sum[x]-sum[p]$

然后就可以写成代码实现了，但是发现对于前两种情况 $LCA(u,x),LCA(v,x)$ 中深度较大的节点 $p$ 就是 $x$，贡献其实就是 $sum[x]-sum[p]=0$

所以直接求 $p$ 就行，不用分情况讨论了

因为一个节点可以被多次插入，所以要用 $multiset$，$multiset$ 里节点按 $dfn$ 排序就可以直接找前驱后继了

具体看代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int n,m,Q;

vector <int> V[N],add[N],del[N];

int dfn[N],F[][N],dep[N],sz[N],cnt;

ll sum[N],ans;

void dfs1(int x)

{

    sz[x]=; dfn[x]=++cnt; ans+=dep[x]-;

    for(int i=;i<=;i++) F[i][x]=F[i-][F[i-][x]];

    for(int v : V[x])

    {

        if(v==F[][x]) continue;

        F[][v]=x; dep[v]=dep[x]+;

        dfs1(v); sz[x]+=sz[v];

    }

}

void dfs2(int x)

{

    sum[x]=sum[F[][x]]+(dep[x]>)*sz[x];

    for(int v : V[x]) if(v!=F[][x]) dfs2(v);

}

inline int LCA(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=;i>=;i--)

        if(dep[F[i][x]]>=dep[y]) x=F[i][x];

    if(x==y) return x;

    for(int i=;i>=;i--)

        if(F[i][x]!=F[i][y]) x=F[i][x],y=F[i][y];

    return F[][x];

}

//以上预处理一堆东西

struct dat{

    int val,x;

    dat (int v=,int xx=) { val=v,x=xx; }

    inline bool operator < (const dat &tmp) const {

        return val<tmp.val;

    }

};

multiset <dat> S;

multiset <dat>::iterator it;

inline int Find(int x)//求x与当前虚树的交点p

{

    dat res; it=S.upper_bound(dat(dfn[x],x)); int lca;

    //注意上面的res和set里面的节点没有关系，只是为了方便更新res

    if(it!=S.end())//注意判越界

        lca=LCA(x,(*it).x),res=max(res,dat(dep[lca],lca));

    if(it!=S.begin())

        lca=LCA(x, (*prev(it)).x ),res=max(res,dat(dep[lca],lca));

        //上面的 prev(it) 是找到与it-1指针不同的最后一个位置

    return res.x ? res.x : x;

}

int main()

{

    n=read(),m=read(),Q=read(); int a,b,c;

    for(int i=;i<n;i++)

    {

        a=read(),b=read();

        V[a].push_back(b); V[b].push_back(a);

    }

    while(Q--)

    {

        a=read(),b=read(),c=read();

        add[a].push_back(c); del[b+].push_back(c);

    }

    dep[]=; dfs1(); dfs2(); S.insert(dat(dfn[],));//初始有根节点

    for(int i=;i<=m;i++)

    {

        for(int x : add[i])

        {

            if(S.find(dat(dfn[x],x))==S.end()) ans-=(sum[x]-sum[Find(x)]);//第一次插入

            S.insert(dat(dfn[x],x));

        }

        for(int x : del[i])

        {

            S.erase(S.find( dat(dfn[x],x) ));

            if(S.find(dat(dfn[x],x))==S.end()) ans+=(sum[x]-sum[Find(x)]);//同理

        }

        printf("%lld ",ans);

    }

    printf("\n");

    return ;

}

巴特西

hihocoder1954 : 压缩树

最新文章

热门文章