【bzoj3779】重组病毒

2015.06.11 13:12 Thu | 16次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定一颗树,根为1,每个点的颜色不同。有下列三种操作:1.把一个点到根的颜色改为一种新的颜色,2.在1的基础上把这个点设为根,3.查询某个点的所有子节点中到根的路径上不同的颜色数的平均值。n<=10000,操作<=10000
题解
看着这些操作是不是特别像一种数据结构?没错,就是LINK-CUT-TREE!第一个操作和第二个操作恰好模拟了lct的access和movetoroot操作,而每个点到根节点的不同的颜色数就是经过的虚边的个数加1.
于是我们可以把dfs序建成线段树,每次切换虚实边的时候把对应的节点在线段树上的区间+1或者-1就行了。
换根之后再在线段树更新时需要用到lca,如果设要更新的节点时x,当前根为root,若x==root,直接更新整段,若lca(x,root)不等于x,说明root不在x的子树中,x子树没有变,直接更新st[x]到ed[x],若root在x的子树中,求出root到x的路径上到达x的前一个点,那么需要更新的就是除了这个点的st[x]到ed[x]的区间的所有点。画个简单的"^"形的图就可以理解了。
tmd这已经是第二次把
rotate(is(y)==is(x)?y:x)
写成
rotate(is(y)==is(x))
这玩意了……
4820B的代码,在A的人里是最短的了……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls son[x][0]
#define rs son[x][1]
#define ll long long
#define isroot(x) (son[father[x]][0]!=x&&son[father[x]][1]!=x)
#define is(x) (son[father[x]][1]==x)
using namespace std;
int n,m,root=1;
char s[20];
struct edge
{
    int to,next;
}e[N<<1];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int st[N],ed[N],dep[N],a[N],fa[N][18],dfn;
ll sum[N<<2],mark[N<<2];
int stack[N],top,rev[N],son[N][2],father[N];
int get_lca(int x,int y)
{
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    int t=dep[x]-dep[y];
    for(int i=0;i<18;i++) if(t&(1<<i)) x=fa[x][i];
    if(x==y) return x;
    for(int i=17;i>=0;i--)
    if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int get_lca2(int x,int y)
{
    for(int i=17;i>=0;i--)
        if(dep[fa[y][i]]>dep[x]) y=fa[y][i];
    return y;
}
void dfs(int u)
{
    dep[u]=dep[father[u]]+1;st[u]=++dfn;
    int i;
    for(i=1;i<18;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(i=h[u];e[i].to;i=e[i].next)
    if(!dep[e[i].to])
    {
        fa[e[i].to][0]=father[e[i].to]=u;
        dfs(e[i].to);
    }
    ed[u]=dfn;
}
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int l)
{
    if(mark[rt])
    {
        mark[rt<<1]+=mark[rt];
        mark[rt<<1|1]+=mark[rt];
        sum[rt<<1]+=mark[rt]*(l-(l>>1));
        sum[rt<<1|1]+=mark[rt]*(l>>1);
        mark[rt]=0;
    }
}
void build_tree(int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build_tree(lson);build_tree(rson);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int val)
{
    if(L<=l&&R>=r)
    {
        sum[rt]+=(r-l+1)*val;
        mark[rt]+=val;
        return;
    }
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(lson,L,R,val);
    if(R>mid) update(rson,L,R,val);
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R)
{
    if(L<=l&&R>=r) return sum[rt];
    pushdown(rt,r-l+1);
    int mid=(l+r)>>1;ll ret=0;
    if(L<=mid) ret=query(lson,L,R);
    if(R>mid) ret+=query(rson,L,R);
    return ret;
}
void change(int x,int v)
{
    if(x==root) update(1,n,1,1,n,v);
    int lca=get_lca(x,root);
    if(lca!=x) update(1,n,1,st[x],ed[x],v);
    else
    {
        lca=get_lca2(x,root);
        if(st[lca]>1) update(1,n,1,1,st[lca]-1,v);
        if(ed[lca]<n) update(1,n,1,ed[lca]+1,n,v);
    }
}
double get_ans(int x)
{
    ll ret=0,siz=0;
    if(x==root) return (double)query(1,n,1,1,n)/(double)n;
    int lca=get_lca(x,root);
    if(lca!=x) return (double)query(1,n,1,st[x],ed[x])/(double)(ed[x]-st[x]+1);
    else
    {
        lca=get_lca2(x,root);
        if(st[lca]>1) ret=query(1,n,1,1,st[lca]-1),siz=st[lca]-1;
        if(ed[lca]<n) ret+=query(1,n,1,ed[lca]+1,n),siz+=n-ed[lca];
        return (double)ret/(double)(siz);
    }
}
void reverse(int x)
{
    if(!x) return;
    swap(ls,rs);
    rev[x]^=1;
}
void push_down(int x)
{
    if(rev[x])
    {
        reverse(ls);
        reverse(rs);
        rev[x]=0;
    }
}
void pushpath(int x)
{
    for(top=0;!isroot(x);x=father[x]) stack[++top]=x;
    stack[++top]=x;
    while(top) push_down(stack[top--]);
}
void link(int x,int y,int d)
{
    father[x]=y;son[y][d]=x;
}
void rotate(int x)
{
    int y=father[x],z=father[y],id=is(x),t=son[x][!id];
    if(!isroot(y)) link(x,z,is(y)); 
    else father[x]=z;
    link(t,y,id);link(y,x,!id);
    son[0][0]=son[0][1]=father[0]=0;
}
void splay(int x)
{
    pushpath(x);
    int y,z;
    while(!isroot(x))
    {
        y=father[x];z=father[y];
        if(isroot(y))
        {
            rotate(x);
            break;
        }
        rotate(is(y)==is(x)?y:x);rotate(x);
    }
}
int find(int x)
{
    pushpath(x);
    while(ls) x=ls,push_down(x);
    return x;
}
void access(int x)
{
    int p=0;
    while(x)
    {
        splay(x);
        if(rs) change(find(rs),1);
        if(p) change(find(p),-1);
        rs=p;p=x;x=father[x];
    }
}
void movetoroot(int x)
{
    access(x);
    splay(x);
    reverse(x);
    root=x;
}
int main()
{
    //freopen("recompile.in", "r", stdin);
    //freopen("recompile.out", "w", stdout);
    cin>>n>>m;
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    dfs(1);
    for(int i=1;i<=n;i++) a[st[i]]=dep[i];
    build_tree(1,n,1);
    int x;
    while(m--)
    {
        scanf("%s%d",s,&x);
        if(s[2]=='L') access(x);
        else if(s[2]=='C') movetoroot(x);
        else printf("%.10lf\n",get_ans(x));
    }
    return 0;
}```