题目概述

维护森林，每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。

解题报告

刚开始竟然极其斯波的想成了路径权值和的 $size$ 倍……把一条路径排成序列，那么很明显贡献和是 $\sum_{i=1}^{Size}i(Size+1-i)a_i$ 。

这怎么用LCT维护啊……完全不可维护啊……所以我们需要一些辅助数组把这个式子构造成一些可维护的格式。

一个节点左子树原先的贡献是 $\sum_{i=1}^{Size_L}i(Size_L+1-i)a_i$ ，加上当前节点还有右子树之后 $Size_L+1-i$ 就变成了 $Size_L+1+Size_R-i$ 。也就是对于每个 $i$ ，增加了 $(Size_R+1)a_i$ 。所以我们拆成 $\sum_{i=1}^{Size_L}ia_i$ 和 $(Size_R+1)Sum_L$ 就变成两个可以维护的东西了，将 $\sum_{i=1}^{Size}ia_i$ 记为 $LS$ 。右子树同理，将 $\sum_{i=1}^{Size}a_{Size-i+1}$ 记为 $RS$。

那么当前节点的总贡献 $val$ 就是 $val_L+val_R+LS_L(Size_R+1)+RS_R(Size_L+1)$ 。

至于打tag，需要用到一个公式 $\sum_{i=1}^{n}i(n-i+1)={n(n+1)(n+2)\over 6}$ ，可以用平方和公式推出。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=50000;

int n,te,a[maxn+5],si[maxn+5],son[maxn+5][2],fa[maxn+5],tag[maxn+5];
ULL sum[maxn+5],LS[maxn+5],RS[maxn+5],val[maxn+5];bool flip[maxn+5];

#define is_ro(p) ((p)!=son[fa[p]][0]&&(p)!=son[fa[p]][1])
#define Son(p) ((p)==son[fa[p]][1])
inline void Pushup(int p){
    si[p]=si[son[p][0]]+1+si[son[p][1]];sum[p]=sum[son[p][0]]+a[p]+sum[son[p][1]];
    LS[p]=LS[son[p][0]]+(ULL)a[p]*(si[son[p][0]]+1)+LS[son[p][1]]+sum[son[p][1]]*(si[son[p][0]]+1);
    RS[p]=RS[son[p][1]]+(ULL)a[p]*(si[son[p][1]]+1)+RS[son[p][0]]+sum[son[p][0]]*(si[son[p][1]]+1);
    val[p]=val[son[p][0]]+val[son[p][1]]+(ULL)a[p]*(si[son[p][0]]+1)*(si[son[p][1]]+1)+LS[son[p][0]]*(si[son[p][1]]+1)+RS[son[p][1]]*(si[son[p][0]]+1);
}
inline void Addflip(int p) {flip[p]^=1;swap(son[p][0],son[p][1]);swap(LS[p],RS[p]);}
inline void Addtag(int p,int x){
    a[p]+=x;sum[p]+=(ULL)x*si[p];LS[p]+=(ULL)x*si[p]*(si[p]+1)>>1;RS[p]+=(ULL)x*si[p]*(si[p]+1)>>1;
    val[p]+=(ULL)x*si[p]*(si[p]+1)*(si[p]+2)/6;tag[p]+=x;
}
inline void Pushdown(int p){
    if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]^=1;
    if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;
}
inline void Rotate(int t){
    int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
    if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Splay(int p){
    static int top,stk[maxn+5];stk[top=1]=p;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
inline void Link(int x,int y) {Makero(x);fa[x]=y;}
inline void Cut(int x,int y) {Makero(x);Access(y);Splay(x);son[x][1]=fa[y]=0;Pushup(x);}
inline int getfa(int x) {Access(x);Splay(x);while (Pushdown(x),son[x][0]) x=son[x][0];return x;}
inline void Update(int x,int y,int w) {Makero(x);Access(y);Splay(x);Addtag(x,w);}
inline int Size(int x,int y) {Makero(x);Access(y);Splay(x);return si[x];}
inline ULL Val(int x,int y) {Makero(x);Access(y);Splay(x);return val[x];}
ULL gcd(ULL a,ULL b) {return b?gcd(b,a%b):a;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1;i<=n;i++) scanf("%d",&a[i]),Pushup(i);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Link(x,y);
    for (int op,x,y,z;te;te--){scanf("%d%d%d",&op,&x,&y);
        if (op==1) {if (Size(x,y)==2) Cut(x,y);}
        else if (op==2) {if (getfa(x)!=getfa(y)) Link(x,y);}
        else if (op==3) {scanf("%d",&z);if (getfa(x)==getfa(y)) Update(x,y,z);} else{
            if (getfa(x)!=getfa(y)) {puts("-1");continue;}ULL U=Val(x,y),D=Size(x,y);D=D*(D+1)>>1;
            ULL t=gcd(U,D);printf("%llu/%llu\n",U/t,D/t);
        }
    }return 0;
}