GDOI 2016 Day1 T4 瘋狂動物城

Description

給出一個N個節點的數，和M次操作。每次操作的類型如下：

1,x,y,z，将x到y的路徑上的ai加上z

2,x,y，詢問x到y的路徑上，ai*(1+2+..+n-i)的和

3,x，将所有的a變更回第x次修改之後的狀态。

強制線上。

N,M<=10^5.

Solution

碼農題（hehe）

愉快的農民生活

先考慮一下序列上的問題。

Ans=∑i=1nai∗(n−i+1)∗(n−i)/2

展開得 Ans=12∑i=1nai∗i2−ai∗i∗(2∗n+1)+ai∗n∗(n+1)

發現 ai∗i2 , ai∗i , ai 的系數都是常數，于是維護這個東西就可以了。

合并自行YY（看Code）

修改也可以愉快的解決了。

放到樹上呢？

樹鍊剖分！

而且要有方向，要寫兩遍。。。

碼量已經起飛。。。

等等，3操作呢？

可持久化（區間修改+lazy标記）

辣眼睛嗆鼻子排宿便清腸道。。。。（王尼瑪上身）

祝君碼的愉快O(∩_∩)O~

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 100005
using namespace std;
typedef long long ll;
const int mo=;
const int inf=;
const ll n2=;
int n,m,l,x,y,z,now,tot,cnt,bz;
int a[N],c[N*3],le[N*50],ri[N*50],root[N];
int son[N],size[N],top[N],w[N],d[N],fa[N][];
int t[N*2],next[N*2],last[N],p[N*50],lazy[N*50];
ll ans;
ll mult(ll x,ll y) {
    if (x%3) return y / %mo*x%mo;
    else return x/%mo*y%mo;
}
struct dd{
    ll sqr,sum,tot,len;
    void clear() {sqr=sum=tot=len=;}
    void add(ll z) {
        tot=(tot+len*z%mo)%mo;
        sum=(sum+len*(len+)%mo*n2%mo*z%mo)%mo;
        sqr=(sqr+mult(len*(len+)/,*len+)*z%mo)%mo;
    }
    friend dd operator+(dd y,dd z) {
        dd x;
        x.len=y.len+z.len;
        x.tot=(y.tot+z.tot)%mo;
        x.sum=(y.sum+y.tot*z.len%mo+z.sum)%mo;
        x.sqr=(y.sqr+*z.len*y.sum%mo+z.len*z.len%mo*y.tot%mo+z.sqr)%mo;
        return x;
    }
}an,key;
struct note{dd up,down;}tr[N*50],zero;
void add(int x,int y) {
    t[++l]=y;next[l]=last[x];last[x]=l;
}
void dfs(int x,int y) {
    int k=;size[x]=;d[x]=d[y]+;fa[x][]=y;
    rep(i,x) if (t[i]!=y) {
        dfs(t[i],x);size[x]+=size[t[i]];
        if (size[t[i]]>k) k=size[t[i]],son[x]=t[i];
    }
}
void make(int x,int y) {
    top[x]=y;w[x]=++tot;c[tot]=x;
    if (!son[x]) return;
    make(son[x],y);
    rep(i,x) if (t[i]!=fa[x][]&&t[i]!=son[x]) make(t[i],t[i]);
}
int lca(int x,int y) {
    if (d[x]<d[y]) swap(x,y);
    fd(j,,) if (d[fa[x][j]]>d[y]) x=fa[x][j];
    if (d[x]!=d[y]) x=fa[x][];
    fd(j,,) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
    if (x!=y) return fa[x][];else return x;
}
int len(int x,int y) {
    int z=lca(x,y);
    return d[x]+d[y]-*d[z]+;
}
void back(int &v,int rt,ll z) {
    if (!v) return;
    tr[++tot]=tr[v];
    le[tot]=le[v];ri[tot]=ri[v];
    p[tot]=rt;lazy[tot]=lazy[v]+z;v=tot;
    tr[v].up.add(z);
    tr[v].down.add(z);
}
void down(int v) {
    if (lazy[v]) {
        back(le[v],p[v],lazy[v]);
        back(ri[v],p[v],lazy[v]);
        lazy[v]=;
    }
}
note merge(note y,note z) {
    note x;
    x.down=z.down+y.down;
    x.up=y.up+z.up;
    return x;
}
void build(int &v,int l,int r) {
    tr[++tot]=tr[v];v=tot;
    if (l==r) {
        tr[v].down.len=tr[v].up.len=;
        tr[v].down.tot=tr[v].up.tot=a[c[l]];
        tr[v].down.sum=tr[v].up.sum=a[c[l]];
        tr[v].down.sqr=tr[v].up.sqr=a[c[l]];
        return;
    }
    int m=(l+r)/;
    build(le[v],l,m);build(ri[v],m+,r);
    tr[v]=merge(tr[le[v]],tr[ri[v]]);
}
void revise(int &v,int l,int r,int x,int y,ll z) {
    int m=(l+r)/;down(v);
    if (l==x&&r==y){back(v,cnt,z);return;}
    if (p[v]!=cnt) {
        tr[++tot]=tr[v];
        le[tot]=le[v];ri[tot]=ri[v];
        p[tot]=cnt;v=tot;
    }
    if (y<=m) revise(le[v],l,m,x,y,z);
    else if (x>m) revise(ri[v],m+,r,x,y,z);
    else revise(le[v],l,m,x,m,z),revise(ri[v],m+,r,m+,y,z);
    tr[v]=merge(tr[le[v]],tr[ri[v]]);
}
void change(int x,int y,int z) {
    int f1=top[x],f2=top[y];root[++cnt]=root[now];
    while (f1!=f2) {
        if (d[f1]<d[f2]) swap(f1,f2),swap(x,y);
        revise(root[cnt],,n,w[f1],w[x],z);
        x=fa[f1][];f1=top[x];
    }
    if (d[x]>d[y]) swap(x,y);
    revise(root[cnt],,n,w[x],w[y],z);
    now=cnt;
}
note find(int v,int l,int r,int x,int y) {
    if (!v) return zero;
    int m=(l+r)/;down(v);
    if (l==x&&r==y) return tr[v];
    if (y<=m) return find(le[v],l,m,x,y);
    else if (x>m) return find(ri[v],m+,r,x,y);
    else return merge(find(le[v],l,m,x,m),find(ri[v],m+,r,m+,y));
}
void query(int x,int y) {
    an.clear();key.clear();
    int f=top[x];int z=lca(x,y);
    while (d[f]>d[z]) {
        an=find(root[now],,n,w[f],w[x]).up+an;
        x=fa[f][];f=top[x];
    }f=top[y];
    while (d[f]>d[z]) {
        key=key+find(root[now],,n,w[f],w[y]).down;
        y=fa[f][];f=top[y];
    }
    if (d[x]>d[y]) an=find(root[now],,n,w[y],w[x]).up+an;
    else key=key+find(root[now],,n,w[x],w[y]).down;
    an=key+an;
}
int main() {
    freopen("zootopia.in","r",stdin);
    freopen("zootopia.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,,n-) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    fo(i,,n) scanf("%d",&a[i]);
    dfs(,);make(,);tot=;
    fo(j,,) fo(i,,n) fa[i][j]=fa[fa[i][j-]][j-];
    build(root[],,n);
    for(;m;m--) {
        scanf("%d",&bz);
        if (bz==) {
            scanf("%d%d%d",&x,&y,&z);
            x^=ans;y^=ans;
            change(x,y,z);
        } else if (bz==) {
            scanf("%d%d",&x,&y);x^=ans;y^=ans;
            query(x,y);ll L=len(x,y);
            ans=(L*(L+)%mo*an.tot%mo-(*L+)*an.sum%mo+an.sqr+mo)%mo;
            ans=(ans*n2)%mo;
            printf("%lld\n",ans);
        } else scanf("%d",&x),now=x^ans;
    }
}