BZOJ3091: 城市旅行

BZOJ3091: 城市旅行

https://lydsy.com/JudgeOnline/problem.php?id=3091

分析:

• 沙雕\(lct\)题，维护一坨信息。
• 其实也不是很多，维护答案，前缀和的和，后缀和的和，总和，\(siz\)。
• 注意翻转标记下传时要交换前缀后缀的信息。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <iostream>
using namespace std;
typedef long long ll;
#define N 50050
#define ls ch[p][0]
#define rs ch[p][1]
#define get(x) (ch[f[x]][1]==x)
#define isrt(x) (ch[f[x]][1]!=x&&ch[f[x]][0]!=x)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define db(x) cerr<<#x<<" = "<<x<<endl
int n,m,ch[N][2],f[N],rev[N];
map<pii,int>MP;
ll sum[N],lx[N],rx[N],tag[N],siz[N],val[N],s1[N],cc[N],ss[N],tot[N];
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
//s1=\sum\i     ss[n]=\sum\i*i     cc[n]=\sum\i*(n-i+1)
inline void pushup(int p) {
    siz[p]=siz[ls]+siz[rs]+1;
    tot[p]=tot[ls]+tot[rs]+val[p];
    lx[p]=lx[ls]+(tot[ls]+val[p])*(siz[rs]+1)+lx[rs];
    rx[p]=rx[rs]+(tot[rs]+val[p])*(siz[ls]+1)+rx[ls];
    sum[p]=sum[ls]+sum[rs]+val[p]*(siz[ls]+1)*(siz[rs]+1)+ rx[ls]*(siz[rs]+1) + lx[rs]*(siz[ls]+1);
}
inline void giv1(int p,ll d) {
    tag[p]+=d; val[p]+=d;
    tot[p]+=siz[p]*d;
    sum[p]+=d*cc[siz[p]];
    lx[p]+=d*s1[siz[p]];
    rx[p]+=d*s1[siz[p]];
}
inline void giv2(int p) {
    swap(lx[ls],rx[ls]);
    swap(lx[rs],rx[rs]);
    swap(ls,rs); 
    rev[p]^=1;
}
inline void pushdown(int p) {
    if(tag[p]) {
        if(ls) giv1(ls,tag[p]);
        if(rs) giv1(rs,tag[p]);
        tag[p]=0;
    }
    if(rev[p]) {
        if(ls) giv2(ls);
        if(rs) giv2(rs);
        rev[p]=0;
    }
}
void UPD(int p) {
    if(!isrt(p)) UPD(f[p]);
    pushdown(p);
}
void rotate(int x) {
    int y=f[x],z=f[y],k=get(x);
    if(!isrt(y)) ch[z][ch[z][1]==y]=x;
    ch[y][k]=ch[x][!k]; f[ch[y][k]]=y;
    ch[x][!k]=y; f[y]=x; f[x]=z;
    pushup(y); pushup(x);
}
void splay(int x) {
    UPD(x);
    for(int d;d=f[x],!isrt(x);rotate(x)) 
        if(!isrt(d)) rotate(get(x)==get(d)?d:x);
}
void access(int p) {
    int t=0;
    while(p) {
        splay(p);
        rs=t; t=p; pushup(p); p=f[p];
    }
}
void makeroot(int p) {
    access(p); splay(p); giv2(p);
}
void link(int x,int p) {
    makeroot(x); splay(x); f[x]=p;
}
void cut(int x,int p) {
    makeroot(x); access(p); splay(p); ls=f[x]=0;
}
int find(int p) {
    access(p); splay(p); while(ls) pushdown(p),p=ls; splay(p); return p;
}
int main() {
    // freopen("ink.in","r",stdin);
    // freopen("ink.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i,x,y;
    for(i=1;i<=n;i++) s1[i]=ll(i)*(i+1)/2;
    for(i=1;i<=n;i++) ss[i]=ss[i-1]+ll(i)*i;
    for(i=1;i<=n;i++) cc[i]=(i+1)*s1[i]-ss[i];
    for(i=1;i<=n;i++) scanf("%lld",&val[i]),pushup(i);
    for(i=1;i<n;i++) {
        scanf("%d%d",&x,&y);
        link(x,y);
        if(x>y) swap(x,y);
        MP[mp(x,y)]=1;
    }
    int opt;
    while(m--) {
        scanf("%d%d%d",&opt,&x,&y);
        if(x>y) swap(x,y);
        if(opt==1) {
            if(!MP.count(mp(x,y))||!MP[mp(x,y)]) continue;
            cut(x,y); MP[mp(x,y)]=0;
        }else if(opt==2) {
            if(find(x)==find(y)) continue;
            link(x,y); MP[mp(x,y)]=1;
        }else if(opt==3) {
            int d;
            scanf("%d",&d);
            if(find(x)!=find(y)) continue;
            makeroot(x); access(y); splay(y);
            giv1(y,d);
        }else {
            if(find(x)!=find(y)) {
                puts("-1"); continue;
            }
            makeroot(x); access(y); splay(y);
            ll re=sum[y], s=siz[y]*(siz[y]+1)/2;
            ll cd=gcd(re,s);
            re/=cd, s/=cd;
            printf("%lld/%lld\n",re,s);
        }
    }
}
/*
4 5 
1 3 2 5
1 2
1 3
2 4
4 2 4
1 2 4
2 3 4
3 1 4 1
4 1 4
*/

BZOJ3091: 城市旅行

原文：https://www.cnblogs.com/suika/p/10092499.html