题解 CF960H 【Santa's Gift】

大菜鸡fks · 2018-08-23 14:48:28 · 题解

柿子裂开以后维护和

标记下传自己拆开（x+y）^2的柿子就可以yy出来了

#include<cstdio>
#define int long long
#define db double
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
const int N=1e5+5;
int rt[N],c[N],n,m,q,C,f[N],head[N],tot;
struct edge{
    int link,next;
}e[N<<1];
inline void add_edge(int u,int v){e[++tot]=(edge){v,head[u]}; head[u]=tot;}
inline void insert(int u,int v){add_edge(u,v); add_edge(v,u);} 
inline void init(){
    n=read(); m=read(); q=read(); C=read();
    for (int i=1;i<=n;i++) f[i]=read();
    for (int i=2;i<=n;i++) insert(read(),i);
}
struct node{
    int sum1,sum2,son[2],plu;
}a[N*100];
int fa[N],cnt,sz[N],Son[N],top[N],dfn[N],pos[N];
void dfs(int u,int Fa){
    fa[u]=Fa; sz[u]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].link;
        if (v!=Fa) {
            dfs(v,u),sz[u]+=sz[v]; 
            if (!Son[u]||sz[Son[u]]<Son[v]) Son[u]=v;
        }
    }
} 
inline int sqr(int x){return x*x;}
inline void pushup(int k){
    int l=a[k].son[0],r=a[k].son[1];
    a[k].sum1=a[l].sum1+a[r].sum1;
    a[k].sum2=a[l].sum2+a[r].sum2;
} 
inline void plus(int &k,int l,int r,int w){
    if (!k) k=++cnt; a[k].plu+=w; int sz=r-l+1;
    a[k].sum2+=a[k].sum1*w+sz*sqr(w); a[k].sum1+=sz*w*2;
}
inline void pushdown(int k,int l,int mid,int r){
    if (a[k].plu){
        plus(a[k].son[0],l,mid,a[k].plu);
        plus(a[k].son[1],mid+1,r,a[k].plu);
        a[k].plu=0;
    }
}
void update(int &k,int l,int r,int x,int y,int w){
    if (!k) k=++cnt;
    if (l==r) {plus(k,l,r,w); return;}
    int mid=(l+r)>>1; pushdown(k,l,mid,r);
    if (mid>=y) update(a[k].son[0],l,mid,x,y,w);
        else if (mid<x) update(a[k].son[1],mid+1,r,x,y,w);
            else update(a[k].son[0],l,mid,x,mid,w),update(a[k].son[1],mid+1,r,mid+1,y,w);
    pushup(k);
}
void Dfs(int u,int tp){
    dfn[u]=++tot; top[u]=tp; pos[tot]=u;
    if (Son[u]) Dfs(Son[u],tp);
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].link;
        if (v!=Son[u]&&v!=fa[u]) Dfs(v,v);
    }
}
inline void Update(int x,int opt,int w){
    for (;x;x=fa[top[x]]){
        int L=dfn[top[x]],R=dfn[x]; update(rt[opt],1,n,L,R,w);
    }
}
inline int calc(int x){
    return sqr(c[x])*a[rt[x]].sum2-a[rt[x]].sum1*C*c[x]+n*sqr(C); 
}
inline void solve(){
    tot=0; dfs(1,0); Dfs(1,1);
    for (int i=1;i<=m;i++) c[i]=read();
    for (int i=1;i<=n;i++) Update(i,f[i],1);
    for (int i=1;i<=q;i++){
        int opt=read(),x=read(),y;
        if (opt==1) {
            y=read(); Update(x,f[x],-1); Update(x,f[x]=y,1); 
        }else{
            int tmp=calc(x);
            printf("%.7lf\n",(db)tmp/(db)n);
        }
    }
}
signed main(){
    init();
    solve();
    return 0;
}