【LCT】BZOJ3091 城市旅行

3091: 城市旅行

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1927  Solved: 631
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

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

Sample Output

16/3
6/1

HINT

对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N

题解

这题和BZOJ2752类似，只不过那个是在序列上而这个在链上，所以没做过2752的话可以先看看这里

我们发现每次询问其实就是算每个点对答案的贡献/C（n+1,2），也就是/（n+1）*n/2

所以每次只需要单独算每个点的贡献即可

然后每个点对答案的贡献就是a[i]*i*(n-i+1)

所以我们维护一个sum，一个siz，一个L=a[i]*i，一个R=a[i]*(n-i+1)

转移挺好想的（逃

代码

//by 减维
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<bitset>
#include<set>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<ctime>
#include<algorithm>
#define ll long long
#define il inline
#define rg register
#define db double
#define mpr make_pair
#define maxn 70005
#define inf (1<<30)
#define eps 1e-8
#define pi 3.1415926535897932384626
using namespace std;

int n,m,fa[maxn],son[maxn][2],siz[maxn];
ll val[maxn],sum[maxn],rev[maxn],mar[maxn],L[maxn],R[maxn],ans[maxn];

ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
il bool pdp(int x){return son[fa[x]][1]==x;}
il bool isrt(int x){return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
il void rever(int x){rev[x]^=1;swap(son[x][0],son[x][1]);swap(L[x],R[x]);}

il void upda(int x)
{
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
    sum[x]=sum[son[x][0]]+sum[son[x][1]]+val[x];
    ans[x]=ans[son[x][0]]+ans[son[x][1]]+val[x]*(siz[son[x][0]]+1)*(siz[son[x][1]]+1)+L[son[x][0]]*(siz[son[x][1]]+1)+R[son[x][1]]*(siz[son[x][0]]+1);
    L[x]=L[son[x][0]]+L[son[x][1]]+val[x]*(siz[son[x][0]]+1)+sum[son[x][1]]*(siz[son[x][0]]+1);
    R[x]=R[son[x][1]]+R[son[x][0]]+val[x]*(siz[son[x][1]]+1)+sum[son[x][0]]*(siz[son[x][1]]+1);
}

il void add(int x,ll y)
{
    mar[x]+=y;
    val[x]+=y;
    sum[x]+=y*siz[x];
    ans[x]+=y*(siz[x]+1)*(siz[x]+2)*siz[x]/6;
    L[x]+=y*(siz[x]+1)*siz[x]/2;
    R[x]+=y*(siz[x]+1)*siz[x]/2;
}

il void pdn(int x)
{
    if(rev[x])
    {
        if(son[x][0]) rever(son[x][0]);
        if(son[x][1]) rever(son[x][1]);
        rev[x]=0;
    }
    if(son[x][0]) add(son[x][0],mar[x]);
    if(son[x][1]) add(son[x][1],mar[x]);
    mar[x]=0;
}

il void pd(int x){if(!isrt(x)) pd(fa[x]);pdn(x);}

il void rot(int x)
{
    int f=fa[x],g=fa[f],o=pdp(x);
    if(!isrt(f)) son[g][pdp(f)]=x;fa[x]=g;
    son[f][o]=son[x][!o];fa[son[f][o]]=f;
    son[x][!o]=f;fa[f]=x;
    upda(f),upda(x);
}

il void splay(int x)
{
    pd(x);
    for(;!isrt(x);rot(x))
        if(!isrt(fa[x])) rot(pdp(fa[x])==pdp(x)?fa[x]:x);
}

il void acc(int x)
{
    for(int y=0;x;y=x,x=fa[x])
        splay(x),son[x][1]=y,upda(x);
}

il int find(int x)
{
    acc(x);splay(x);
    while(son[x][0]) pdn(x),x=son[x][0];
    return x;
}

il void bert(int x){acc(x);splay(x);rever(x);}
il void spli(int x,int y){bert(x);acc(y);splay(y);}
il void cut(int x,int y){spli(x,y);fa[x]=son[y][0]=0;upda(y);}
il void link(int x,int y){bert(x);fa[x]=y;}

void dfs(int x)
{
    if(son[x][0]) dfs(son[x][0]);
    printf("%d ",x);
    if(son[x][1]) dfs(son[x][1]);
}

void dfs2(int x)
{
    if(son[x][0]) dfs2(son[x][0]);
    printf("%d ",sum[x]);
    if(son[x][1]) dfs2(son[x][1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&val[i]);
        siz[i]=1;
        sum[i]=val[i];
        ans[i]=val[i];
        L[i]=val[i];
        R[i]=val[i];
    }
    for(int i=1,x,y;i<n;++i) scanf("%d%d",&x,&y),link(x,y);
    ll d;
    for(int i=1,op,x,y;i<=m;++i)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            if(find(x)==find(y)) cut(x,y);
        }else if(op==2){
            if(find(x)!=find(y)) link(x,y);
        }else if(op==3){
            scanf("%lld",&d);
            if(find(x)==find(y))spli(x,y),add(y,d);
        }else{
            if(find(x)!=find(y)) puts("-1");
            else{
                spli(x,y);
                ll ans1=ans[y];
                ll ans2=siz[y]*(siz[y]+1)/2;
                ll gc=gcd(ans1,ans2);
                printf("%lld/%lld
",ans1/gc,ans2/gc);
            }
        }
    }
    return 0;
}