【bzoj3091】【未完】城市旅行

2015.04.14 19:41 Tue | 4次阅读 | 旧日oi | 固定链接 | 源码

Description

.jpg)

Input

.jpg)

Output

.jpg)

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

题解

我是把这道题当练习LCT的模板写的,所以中间那些球期望的东西就是看POPOQQQ大爷的题解了,先留个坑吧
写lct传标记的时候一定要记得特判会出现0的情况,绝对不要更新……这是数组党的忠告……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 50010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define is(x) (son[fa[x]][1]==x)
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define ls son[x][0]
#define rs son[x][1]
using namespace std;
ll read()
{
    ll x=0,f=1;char 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;
}
int n,m,q;
struct edge{
    int to;
    int next;
}e[maxn<<1];
int h[maxn],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
ll w[maxn],sum[maxn],lsum[maxn],rsum[maxn],ex[maxn],add_mark[maxn];
int fa[maxn],son[maxn][2],size[maxn],stk[maxn],rev_mark[maxn],top;
void dfs(int u,int f)
{
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        fa[v]=u;
        dfs(v,u);
    }
}
void push_up(int x)
{
    size[x]=size[ls]+size[rs]+1;
    sum[x]=sum[ls]+sum[rs]+w[x];
    lsum[x]=lsum[ls]+w[x]*(size[ls]+1)+lsum[rs]+sum[rs]*(size[ls]+1);
    rsum[x]=rsum[rs]+w[x]*(size[rs]+1)+rsum[ls]+sum[ls]*(size[rs]+1);
    ex[x]=ex[ls]+ex[rs]+(size[rs]+1)*lsum[ls]+(size[ls]+1)*rsum[rs]+
            (size[ls]+1)*(size[rs]+1)*w[x];
}
void add(int x,ll t)
{
    if(!x) return;
    w[x]+=t;
    sum[x]+=t*size[x];
    lsum[x]+=t*size[x]*(size[x]+1)/2;
    rsum[x]+=t*size[x]*(size[x]+1)/2;
    ex[x]+=t*size[x]*(size[x]+1)*(size[x]+2)/6;
    add_mark[x]+=t;
}
void reverse(int x)
{
    if(!x) return;
    swap(ls,rs);
    swap(lsum[x],rsum[x]);
    rev_mark[x]^=1;
}
void push_down(int x)
{
    if(rev_mark[x])
    {
        reverse(ls);
        reverse(rs);
        rev_mark[x]=0;
    }
    if(add_mark[x])
    {
        add(ls,add_mark[x]);
        add(rs,add_mark[x]);
        add_mark[x]=0;
    }
}
void push_path(int x)
{
    for(top=0;!isroot(x);x=fa[x]) stk[++top]=x;
    stk[++top]=x;
    while(top) push_down(stk[top--]);
}
void connect(int x,int y,int d)
{
    son[y][d]=x;fa[x]=y;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
    if(isroot(y)) fa[x]=z;
    else connect(x,z,is(y));
    connect(t,y,id);connect(y,x,!id);
    son[0][0]=son[0][1]=fa[0]=0;
    push_up(y);
}
void splay(int x)
{
    push_path(x);
    while(!isroot(x))
    {
        int y=fa[x];
        if(isroot(y))
        {
            rotate(x);
            break;
        }
        rotate(is(y)==is(x)?y:x);
        rotate(x);
    }
    push_up(x);
}
void access(int x)
{
    int p=0;
    while(x)
    {
        splay(x);
        rs=p;
        push_up(x);
        p=x;
        x=fa[x];
    }
}
void makeroot(int x)
{
    access(x);
    splay(x);
    reverse(x);
}
int find_root(int x)
{
    while(fa[x]) x=fa[x];
    return x;
}
void link(int x,int y)
{
    if(find_root(x)==find_root(y)) return;
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y)
{
    if(x==y||find_root(x)!=find_root(y)) return;
    makeroot(y);
    access(x);
    splay(x);
    if(ls==y&&!son[y][1])
    {
        ls=0;
        fa[y]=0;
        push_up(x);
    }
}
void modify(int x,int y,ll t)
{
    if(find_root(x)!=find_root(y)) return;
    makeroot(y);
    access(x);
    splay(x);
    add(x,t);
}
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
void query(int x,int y)
{
    if(find_root(x)!=find_root(y)) 
    {
        puts("-1");
        return;
    }
    makeroot(y);
    access(x);splay(x);
    ll a=ex[x];
    ll b=size[x]*(size[x]+1)/2;
    ll g=gcd(a,b);
    printf("%lld/%lld\n",a/g,b/g);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) 
    {
        w[i]=read();
        sum[i]=lsum[i]=rsum[i]=ex[i]=w[i];
        size[i]=1;
    }
    for(int u,v,i=1;i<n;i++)
    {
        u=read();v=read();
        ae(u,v);ae(v,u);
    }
    dfs(1,0);
    for(int x,y,z,k=1;k<=m;k++)
    {
        q=read();x=read();y=read();
        if(q==1) cut(x,y);
        else if(q==2) link(x,y);
        else if(q==3) z=read(),modify(x,y,z);
        else query(x,y);
    }
    return 0;
}```