BZOJ 3091シティツアーLCT

タイトル:リンク
方法:LCT
解析:
もしbzoj 2752がやったことがないなら、まずその問題をすることをお勧めします.
この問題なら、前の3問は裸すぎて何も言わない.
第4の操作は、前の2752の問題に基づいて、私たちは1つのルートノードについて、その左の息子の期待値がすでに知っていて、右の息子の期待値もすでに知っていて、どのようにこのノードの期待値を維持するかを考える必要があります.
popoqqqおじいさんの言うことはとてもはっきりしています!好評
http://blog.csdn.net/popoqqq/article/details/40823659
リンクするのがおっくうなら少しだけ話します.(おじいさんの言うとおりに栗)
以下は2752をやったことがあれば読めるはずです.
左サブツリー
4つのノードがあれば期待される寄与は何ですか.
1*4*a1+2*3*a2+3*2*a3+4*1*a4
さらに右の木に対して
2つのノードが望む寄与は何かを仮定する
1*2*b1+2*1*b2
ルートの値をvalに設定してもいいです
では明らかに合併後は何でしょうか
1*7*a1+2*6*a2+3*5*a3+4*4*a4+5*3*val+6*2*b1+7*1*b2
そしてこの総期待の前4項で元の左子樹期待を減らす
3*(a 1+2*a 2+3*a 3+4*a 4)->3は右サブツリーsize+1
後2項から元の右子樹の期待を差し引く
5*(2*b1+b2);->5は左サブツリーsize+1
真ん中のvalは?
5*3*val->5は左サブツリーsize+1、3は右サブツリーsize+1
だから私たちは何を維持しますか?
1つ目:普通のsum
2つ目:siz
第三種類:1*a 1+2*a 2+3*a 3+4*a 4+…+n*an
第四種類:n*a 1+(n-1)*a 2+(n-2)*a 3+...+1*an
どのように更新しますか?数学の公式ですね.
もう一つの公式は必ず使います
1*n+2*(n-1)+3*(n-2)+…+n*1=n*(n+1)*(n+2)/6
いい問題だ!
コード:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50010
using namespace std;
typedef unsigned long long ll;
ll sum1n[N];
ll sumn1[N];
ll sum[N];
ll siz[N];
int ch[N][2];
ll exp[N];
ll col[N];
ll val[N];
int rt[N];
int fa[N];
int rev[N];
int head[N];
int n,m,cnt;
struct node
{
    int to,next;
}edge[N<<1];
ll gcd(ll a,ll b)
{
    while(b)
    {
        ll t=b;
        b=a%b;
        a=t;
    }
    return a;
}
void pushup(int x)
{
    if(!x)return;
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
    sum1n[x]=sum1n[ch[x][0]]+sum1n[ch[x][1]]+(siz[ch[x][0]]+1)*(sum[ch[x][1]]+val[x]);
    sumn1[x]=sumn1[ch[x][1]]+sumn1[ch[x][0]]+(siz[ch[x][1]]+1)*(sum[ch[x][0]]+val[x]);
    exp[x]=exp[ch[x][0]]+exp[ch[x][1]]+(siz[ch[x][1]]+1)*sum1n[ch[x][0]]+(siz[ch[x][0]]+1)*sumn1[ch[x][1]]+val[x]*(siz[ch[x][0]]+1)*(siz[ch[x][1]]+1);
}
void reverse(int x)
{
    swap(ch[x][0],ch[x][1]);
    swap(sum1n[x],sumn1[x]);
    rev[x]^=1;
}
void pushdown(int x)
{
    if(!x)return;
    if(rev[x])
    {
        reverse(ch[x][0]);
        reverse(ch[x][1]);
        rev[x]=0;
    }
    if(col[x])
    {
        if(ch[x][0]!=0)
        {
            val[ch[x][0]]+=col[x];
            col[ch[x][0]]+=col[x];
            sum[ch[x][0]]+=col[x]*siz[ch[x][0]];
            sum1n[ch[x][0]]+=((1+siz[ch[x][0]])*siz[ch[x][0]]*col[x])/2;
            sumn1[ch[x][0]]+=((1+siz[ch[x][0]])*siz[ch[x][0]]*col[x])/2;
            exp[ch[x][0]]+=(siz[ch[x][0]]*(siz[ch[x][0]]+1)*(siz[ch[x][0]]+2)*col[x])/6;
        }
        if(ch[x][1]!=0)
        {
            val[ch[x][1]]+=col[x];
            col[ch[x][1]]+=col[x];
            sum[ch[x][1]]+=col[x]*siz[ch[x][1]];
            sum1n[ch[x][1]]+=((1+siz[ch[x][1]])*siz[ch[x][1]]*col[x])/2;
            sumn1[ch[x][1]]+=((1+siz[ch[x][1]])*siz[ch[x][1]]*col[x])/2;
            exp[ch[x][1]]+=(siz[ch[x][1]]*(siz[ch[x][1]]+1)*(siz[ch[x][1]]+2)*col[x])/6;
        }
        col[x]=0;
    }
}
void down(int x)
{
    if(!rt[x])down(fa[x]);
    pushdown(x);
}
void rotate(int x)
{
    int y=fa[x],kind=ch[y][1]==x;
    ch[y][kind]=ch[x][!kind];
    fa[ch[y][kind]]=y;
    ch[x][!kind]=y;
    fa[x]=fa[y];
    fa[y]=x;
    if(rt[y])rt[y]=0,rt[x]=1;
    else ch[fa[x]][ch[fa[x]][1]==y]=x;
    pushup(y);
}
void splay(int x)
{
    down(x);
    while(!rt[x])
    {
        int y=fa[x],z=fa[y];
        if(rt[y])rotate(x);
        else if((ch[y][1]==x)==(ch[z][1]==y))rotate(y),rotate(x);
        else rotate(x),rotate(x);
    }
    pushup(x);
}
void access(int x)
{
    int y=0;
    while(x)
    {
        splay(x);
        rt[ch[x][1]]=1,rt[y]=0;
        ch[x][1]=y;
        pushup(x);
        y=x,x=fa[x];
    }
}
int find_root(int x)
{
    while(fa[x])x=fa[x];
    return x;
}
void movetoroot(int x)
{
    access(x);
    splay(x);
    reverse(x);
}
void link(int x,int y)
{
    if(find_root(x)==find_root(y))return;
    movetoroot(x);movetoroot(y);
    fa[x]=y;
}
void cut(int x,int y)
{
    if(find_root(x)!=find_root(y))return;
    movetoroot(x);
    access(y);
    splay(y);
    if(ch[y][0]==x&&ch[x][1]==0)
    {
        fa[x]=0;
        ch[y][0]=0;
        rt[x]=1;
        pushup(y);
    }
}
void dfs(int now,int fffa)
{
    fa[now]=fffa;
    for(int i=head[now];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fffa)continue;
        dfs(to,now);
    }
}
void initedge()
{
    memset(head,-1,sizeof(head));
    cnt=1;
}
void edgeadd(int from,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void init()
{
    initedge();
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&val[i]);
        sum[i]=sum1n[i]=sumn1[i]=exp[i]=val[i];
        siz[i]=rt[i]=1;
    }
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        edgeadd(x,y);edgeadd(y,x);
    }
    dfs(1,0);
}
void update(int x,int y,ll z)
{
    if(find_root(x)!=find_root(y))return;
    movetoroot(x);
    access(y);
    splay(y);
    col[y]+=z;
    val[y]+=z;
    sum[y]+=z*siz[y];
    sum1n[y]+=((1+siz[y])*siz[y]*z)/2;
    sumn1[y]+=((1+siz[y])*siz[y]*z)/2;
    exp[y]+=(siz[y]*(siz[y]+1)*(siz[y]+2)*z)/6;
    pushdown(y);
}
void query(int x,int y)
{
    if(find_root(x)!=find_root(y))
    {
        puts("-1");
        return;
    }
    movetoroot(x);
    access(y);
    splay(y);
    ll ans=exp[y];
    ll tmpcnt=(siz[y]*(siz[y]+1))/2;
    ll tmpgcd=gcd(ans,tmpcnt);
    printf("%llu/%llu
",ans/tmpgcd,tmpcnt/tmpgcd);
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;i++)
    {
        int jd,x,y;
        ll z;
        scanf("%d%d%d",&jd,&x,&y);
        switch(jd)
        {
            case 1:cut(x,y);break;
            case 2:link(x,y);break;
            case 3:
                scanf("%llu",&z);
                update(x,y,z);
                break;
            case 4:
                query(x,y);
                break;
        }
    }
}