【BZOJ】3779 重组病毒

【算法】Link-Cut Tree+线段树(维护DFS序)

【题解】整整三天……T_T

这篇题解比较资瓷：permui

这道题虽然树形态没有变化，但用lct写的原因在于把题目中的操作一进行了神转化：每条重链表示一种颜色，点到根的颜色数=经过的轻链数+1。

询问一个点的子树所有结点到根的代价和(的平均数)，子树问题考虑使用dfs序维护。有要支持子树整体的加减，所以用线段树维护DFS序。

操作一转化之后就相当于access操作(x到根染成一种颜色==x到根在同一重链)，过程中轻变重子树-1，重变轻子树+1，这里的子树是相对于新根的，做法见下。

操作二换根是关键。题目条件刚好先做了access(x)操作，于是我们就可以很方便地换根。问题在于DFS序根据的树形态从一开始就固定下来，那么根据新根root和查询点x在树上的位置关系可以分类讨论：

1.root=x，整棵树。

2.root在x的子树上，整棵树除去root所在子树。

3.x在root的子树上，原x子树。

【注意】

1.代价和很大，long long。

2.线段树放越界：if(l>r)return;

　　下传之前判断是否叶子结点

　　mid是seg的l和r的中点

3.无向边数组开2倍。

3.邻接表记得判父亲。

4.利用DFS序嵌套关系判断子结点。

5.splay上访问前要先下传。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

const int maxn=;

int f[maxn],t[maxn][],dfsnum=,first[maxn],second[maxn],next[maxn],tot,deep[maxn],g[maxn],root,n,m,father[maxn];

struct edge{int u,v,from;}e[maxn*];//无向边数组开两倍！

struct tree{int l,r;long long sum,delta;}tr[maxn*];

int read()

{

    char c;int s=;

    while(!isdigit(c=getchar()));

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s;

}

void insert(int u,int v)

{tot++;e[tot].u=u;e[tot].v=v;e[tot].from=next[u];next[u]=tot;}

void seg_build(int k,int l,int r)

{

    tr[k].l=l;tr[k].r=r;

    if(l==r){tr[k].sum=;return;}

    int mid=(l+r)>>;

    seg_build(k<<,l,mid);

    seg_build(k<<|,mid+,r);

}

void seg_ins(int k,int x)

{tr[k].sum+=1ll*(tr[k].r-tr[k].l+)*x;}

void seg_pushdown(int k)

{

    if(tr[k].delta)

    {

        tr[k<<].delta+=tr[k].delta;

        tr[k<<|].delta+=tr[k].delta;

        seg_ins(k<<,tr[k].delta);

        seg_ins(k<<|,tr[k].delta);

        tr[k].delta=;

    }

}

void seg_insert(int k,int l,int r,int x)

{

    if(l>r)return;//woc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

//  if(tr[k].l==tr[k].r&&l!=tr[k].l&&r!=tr[k].r){return;}//这样写是错的！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！1

    if(l<=tr[k].l&&tr[k].r<=r)

    {

        seg_ins(k,x);

        tr[k].delta+=1ll*x;

        return;

    }

    else

    {

        if(tr[k].l==tr[k].r)return;//防止非法访问！！！但是其实在区间的中间(l+1)也可能出现叶子结点的，所以不能一概而论，只能在这里判断。

        seg_pushdown(k);

        int mid=(tr[k].l+tr[k].r)>>;

        if(l<=mid)seg_insert(k<<,l,r,x);

        if(r>mid)seg_insert(k<<|,l,r,x);

        tr[k].sum=tr[k<<].sum+tr[k<<|].sum;

    }

}

long long seg_query(int k,int l,int r)

{

    if(l>r)return ;//woc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

//  if(tr[k].l==tr[k].r&&l!=tr[k].l&&r!=tr[k].r)return 0;//错误写法！

    if(l<=tr[k].l&&tr[k].r<=r)return tr[k].sum;

    if(tr[k].l==tr[k].r)return ;

    seg_pushdown(k);

    int mid=(tr[k].l+tr[k].r)>>;//mid是seg的中点！

    long long sums=;

    if(l<=mid)sums=seg_query(k<<,l,r);

    if(r>mid)sums+=seg_query(k<<|,l,r);

    return sums;

}

void dfs(int x,int fa)

{

    father[x]=fa;

    f[x]=fa;//开始时每个点自成重链，但是初始根为1，所以父子关系已经串好了。

    first[x]=++dfsnum;

    deep[x]=deep[fa]+;

    seg_insert(,first[x],first[x],deep[x]);

    for(int i=next[x];i;i=e[i].from)if(e[i].v!=fa)//判父亲！！！

    {

        //这棵树的父亲和splay的父亲不能混为一谈。

        dfs(e[i].v,x);

    }

    second[x]=dfsnum;

}

bool isroot(int x)

{return !x||(t[f[x]][]!=x&&t[f[x]][]!=x);}//0也认为它是splay的根。

void pushdown(int x)

{

    if(g[x])

    {

        g[t[x][]]^=;g[t[x][]]^=;

        swap(t[x][],t[x][]);

        g[x]=;

    }

}

void rotate(int x)

{

    int k=x==t[f[x]][];

    int y=f[x];

    t[y][k]=t[x][!k];f[t[x][!k]]=y;

    if(!isroot(y))t[f[y]][y==t[f[y]][]]=x;f[x]=f[y];f[y]=x;

    t[x][!k]=y;

}

int cnt,N[maxn];

void splay(int x)

{

    cnt=;

    int y=x;

    while(!isroot(y))N[++cnt]=y,y=f[y];

    pushdown(y);

    for(int i=cnt;i>=;i--)pushdown(N[i]);

    while(!isroot(x))

    {

        if(isroot(f[x])){rotate(x);return;}

        int X=x==t[f[x]][],Y=f[x]==t[f[f[x]]][];

        if(X^Y)rotate(x),rotate(x);

        else rotate(f[x]),rotate(x);

    }

}

bool inson(int x,int y)//x在y的子树内

{return first[x]>=first[y]&&second[x]<=second[y];}

int wson(int x,int y)//x在y的哪个儿子的子树内

{

    for(int i=next[y];i;i=e[i].from)if(e[i].v!=father[y])

    {

        if(first[x]>=first[e[i].v]&&second[x]<=second[e[i].v])return e[i].v;

    }

    return ;

}

void lct_insert(int x,int num)

{

    if(x==root)seg_insert(,,n,num);else

    if(inson(root,x))

    {

        int p=wson(root,x);

        seg_insert(,,first[p]-,num);

        seg_insert(,second[p]+,n,num);

    }

    else seg_insert(,first[x],second[x],num);

}

int top(int x)

{

    pushdown(x);

    while(t[x][])x=t[x][],pushdown(x);//访问子节点要下传啊！！！

    return x;

}

void access(int x)

{

    int y=;

    while(x)

    {

        splay(x);

        if(t[x][])lct_insert(top(t[x][]),);//随时要注意判断结点是否存在！

        if(y)lct_insert(top(y),-);//root一定是主链的根(最左端结点)，往主链方向靠近的话，重链顶部结点的子树就能自然地覆盖包括整条链。

        t[x][]=y;

        y=x;x=f[x];

    }

}

void center(int x)

{

    splay(x);//必须splay才能定位到主链，方便翻转。

    root=x;

    g[x]^=;//使x成为主链的根,因为access中已经splay了使x成为主链splay的根节点，对x操作就是对主链操作。

}

double query(int x)

{

    if(x==root){return 1.0*seg_query(,,n)/n;}else

    if(inson(root,x))

    {

        int p=wson(root,x);

        return 1.0*(seg_query(,,first[p]-)+seg_query(,second[p]+,n))/(n-(second[p]-first[p]+));

    }

    else return 1.0*seg_query(,first[x],second[x])/(second[x]-first[x]+);

}

char s[];

int main()

{

    n=read();m=read();

    int u,v;

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

    {

        u=read(),v=read();

        insert(u,v);

        insert(v,u);

    }

    root=;//初值！

    seg_build(,,n);

    dfs(,);

    int x;

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

    {

        scanf("%s%d",s,&x);

        if(s[]=='Q')printf("%.10lf\n",query(x));

        else

        {

            access(x);

            if(s[]=='C')center(x);

        }

    }

    return ;

}

巴特西

【BZOJ】3779 重组病毒

最新文章

热门文章