BZOJ 2851: 极限满月虚树 or 树链的并

2851: 极限满月

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 170 Solved: 82
[Submit][Status][Discuss]

Description

BZOJ 2851: 极限满月虚树 or 树链的并-LMLPHP

Input

第一行一个正整数。

之后行描述集合。第一个数表示集合中元素的个数，之后给出集合中的元素。

之后一行一个正整数。

之后行每行描述一个询问。格式与之前相同。

Output

对于每个询问，在单独的一行内输出答案。

Sample Input

7
0
1 1
1 1
1 2
2 2 3
0
2 2 6
3
2 2 3
2 3 5
2 4 5

Sample Output

3
3
4

HINT

/*对于100% 的数据，1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。*/

[Discuss]里的正确数据范围：

n<=200000 m<=200000
A集合元素总个数<=300000
输入总数<=2500000

Source

Violet 0

想法：

如果把Bi当成红点，i当成蓝点，B0为一个虚红点，边V->U为U∈V。因为"a∈Ak=>a<k"，所以每个Bi(i>0)红点只会连一个蓝点与一个红点。因此红点构成一棵树。

显然易见，Bi所连的红点为{Bj|j∈Ai}的lca。于是答案变成求集合{S}中所有红点所包含蓝点的并的大小。因为每个点蓝点只会被一个红点连边，所以可以把蓝点捆在该红点上，答案就变成统计{S}中所有红点的祖先并(除去B0虚红点)的大小。于是可以使用虚树或者树链的并解决。

复杂度O((∑|A|+∑|S|)logn).

细节：你会发现建红点树的过程是动态加点的在线求lca的过程。可以用倍增(仅支持加点)或LCT(支持加点删点换根....)解决。

#include<cmath>

#include<cstdio>

#include<vector>

#include<algorithm>

typedef long long ll;

const int N();

struct Node

{

    int nd,nx;

}bot[N];

int tot,first[N],depth[N],dfn[N],cnt;

void add(int a,int b){bot[++tot]=(Node){b,first[a]};first[a]=tot;}

int F[][N],logg;

int n,m,h[N],S;

std::vector<int>A[N];int sz,x;

template<class T>void read(T&x)

{

    x=;bool f=;char c=getchar();

    while((c<''||c>'')&&c!='-')c=getchar();if(c=='-')f=,c=getchar();

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    x=f?-x:x;

}

void swap(int &x,int &y){if(x==y)return;x^=y;y^=x;x^=y;}

int lca(int a,int b)

{

    if(depth[a]<depth[b])swap(a,b);

//    fprintf(stderr,"a:%d b:%d\b",a,b);

    for(int k=depth[a]-depth[b],j=;k;k>>=,j++)

        if(k&)a=F[j][a];

//    fprintf(stderr,"a:%d b:%d\b",a,b);

    if(a==b)return a;

    for(int j=logg;F[][a]!=F[][b];j--)

    if(F[j][a]!=F[j][b])a=F[j][a],b=F[j][b];

    return F[][a];

}

void relax(int x)

{

    for(int j=;j<=logg&&F[j-][x];j++)

        F[j][x]=F[j-][ F[j-][x] ];

}

namespace GetTree

{

    void init()

    {

        read(n);

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

        {

            read(sz);

            while(sz--) read(x),A[i].push_back(x);

            std::sort(A[i].begin(),A[i].end());

        }

    }

    void build()

    {

        logg=log2(n);

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

        {

            now=n+;

            if(A[i].size())

            {

                now=A[i][];

                for(int v=,sz=A[i].size();v<sz;v++)

                {

//                    fprintf(stderr,"now:%d\n",now);

                    now=lca(now,A[i][v]);

//                    fprintf(stderr,"A:%d\n",A[i][v]);

                }

            }

//            fprintf(stderr,"now:%d\n",now);

            F[][i]=now;depth[i]=depth[now]+;

            add(now,i);

            relax(i);

        }

    }

    void DFS(int x)

    {

        dfn[x]=++cnt;

        for(int v=first[x];v;v=bot[v].nx) DFS(bot[v].nd);

    }

    void run()

    {

        init();

        build();

        DFS(n+);

    }

}

bool cmp(int a,int b){return dfn[a]<dfn[b];}

void total()

{

    std::sort(h+,h+S+,cmp);

    int ans=;

    for(int i=,t;i<=S;i++)

    {

        ans+=depth[h[i]];

//        fprintf(stderr,"ans:%d\n",ans);

        if(i>)

        {

            t=lca(h[i-],h[i]);

            ans-=depth[t];

        }

    }

    printf("%d\n",ans);

}

int main()

{

//    freopen("C.in","r",stdin);

    GetTree::run();

    read(m);

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

    {

        read(S);

        for(int j=;j<=S;j++) read(h[j]);

        total();

    }

    return ;

}

的并