出题人题解 | #树上路径#

原题解链接：

${\sum }_{1⩽i,j⩽N}{a}_i\ast a_j={(\sum a_i)}^2-\sum a_i^2\backslash sum\_\{1\; \backslash leqslant\; i,\; j\; \backslash leqslant\; N\}\; a\_\{i\}\; *\; a\_\{j\}=\backslash left(\backslash sum\; a\_\{i\}\backslash right)^\{2\}-\backslash sum\; a\_\{i\}^\{2\}$

证明可以暴力展开

后面的两项都可以通过树剖打标记维护

第一个直接维护和，询问的时候乘起来即可

第二个可以展开

$\sum {(a_i+b)}^2=\sum a_i^2+\sum 2a_{i}b+siz\ast b^2\backslash sum\backslash left(a\_\{i\}+b\backslash right)^\{2\}=\backslash sum\; a\_\{i\}^\{2\}+\backslash sum\; 2\; a\_\{i\}\; b+s\; i\; z\; *\; b^\{2\}$

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
#define LL long long 
using namespace std;
const LL MAXN = 3 * 1e6;
LL inv = 500000004, mod;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL N, M, root;
LL a[MAXN], b[MAXN];
struct node {
    LL u, v, nxt;
}E[MAXN];
LL head[MAXN], num = 1;
inline void AddEdge(LL x, LL y) {
    E[num].u = x; E[num].v = y;
    E[num].nxt = head[x]; head[x] = num++;
}
LL deep[MAXN], fa[MAXN], siz[MAXN], son[MAXN], topf[MAXN], ID[MAXN], tot;
void dfs1(LL x, LL f) {
//	printf("%d\n", x);
    fa[x] = f; siz[x] = 1;
    for(LL i = head[x]; i != -1; i = E[i].nxt) {
        if(!deep[E[i].v] && E[i].v != f) {
            deep[E[i].v] = deep[x] + 1;
            dfs1(E[i].v, x);
            siz[x] += siz[E[i].v];
            if(siz[E[i].v] > siz[son[x]]) son[x] = E[i].v;
        }
    }
}
void dfs2(LL x,LL topfa) {
    ID[x] = ++tot;
    topf[x] = topfa;
    if(!son[x]) return ;
    dfs2(son[x], topfa);
    for(LL i = head[x]; i != -1; i = E[i].nxt)
        if(!topf[E[i].v])	dfs2(E[i].v, E[i].v);
}
struct Tree {
    LL l, r,  f, siz;
    LL sum1, sum2;
}T[MAXN];
#define ls k<<1
#define rs k<<1|1
void update(LL k) {
    T[k].sum1 = (T[ls].sum1 + T[rs].sum1) % mod;
    T[k].sum2 = (T[ls].sum2 + T[rs].sum2) % mod;
}
void Build(LL k, LL ll, LL rr) {
    T[k].l = ll; T[k].r = rr; T[k].siz = T[k].r - T[k].l + 1;
    if(ll == rr) {T[k].sum1 = a[ll] % mod; T[k].sum2 = a[ll] * a[ll] % mod; return ;}
    LL mid = (T[k].l + T[k].r) >> 1;
    Build(ls, ll, mid); Build(rs, mid + 1, rr);
    update(k);
}
void ps(LL x, LL val) {//tag
    T[x].sum2 = (T[x].sum2 + 2 * val * (T[x].sum1) % mod + T[x].siz * val * val % mod) % mod;
    T[x].sum1 = (T[x].sum1 + val * T[x].siz) % mod;
    T[x].f = (T[x].f + val) % mod;
}
void pushdown(LL k) {
    if(T[k].f) {
        ps(ls, T[k].f); ps(rs, T[k].f);
        T[k].f = 0;
    }
}
void IntervalAdd(LL k, LL ll, LL rr,LL val) {
    if(ll <= T[k].l && T[k].r <= rr) {
        //T[k].sum =  (T[k].sum + T[k].siz * val) % mod;
        ps(k, val);
        return ; 
    }
    pushdown(k);
    LL mid = (T[k].l + T[k].r) >> 1;
    if(ll <= mid) IntervalAdd(ls, ll, rr, val); 
    if(rr >  mid) IntervalAdd(rs, ll, rr, val);
    update(k);
}

LL IntervalSum(LL k, LL ll, LL rr, LL opt) {
    LL ans = 0;
    if(ll <= T[k].l && T[k].r <= rr) {
    	if(opt == 0) ans = (ans + T[k].sum1) % mod; 
    	else ans = (ans + T[k].sum2) % mod;
        return ans;
    }
    pushdown(k);
    LL mid = (T[k].l + T[k].r) >> 1;
    if(ll <= mid) ans = (ans + IntervalSum(ls, ll, rr, opt)) % mod;
    if(rr >  mid) ans = (ans + IntervalSum(rs, ll, rr, opt)) % mod;
    update(k);
    return ans % mod;
}
LL TreeSum(LL x, LL y, LL opt) {
    LL ans = 0;
    while(topf[x] != topf[y]) {
        if(deep[topf[x]] < deep[topf[y]]) swap(x, y);
        ans = (ans + IntervalSum(1, ID[topf[x]], ID[x], opt)) % mod;
        x = fa[topf[x]];
    }
    if(deep[x] < deep[y]) swap(x,y);
    return (ans + IntervalSum(1, ID[y], ID[x], opt)) % mod;
}
void TreeAdd(LL x, LL y, LL val) {
    while(topf[x] != topf[y]) {
        if(deep[topf[x]] < deep[topf[y]]) swap(x, y);
        IntervalAdd(1, ID[topf[x]], ID[x], val);
        x = fa[topf[x]];
    }
    if(deep[x] < deep[y]) swap(x, y);
    IntervalAdd(1, ID[y], ID[x], val);
}
int main() {
    memset(head, -1, sizeof(head));
    N = read(), M = read(), root = 1, mod = 1e9 + 7; 
    for(LL i = 1; i <= N; i++) b[i] = read() % mod;
    for(LL i = 1; i <= N - 1; i++) {
        LL x = read(), y = read();
        AddEdge(x, y); AddEdge(y, x);
    }
    deep[root] = 1;
    dfs1(root, 0);
    dfs2(root, root);
    for(LL i = 1; i <= N; i++) a[ID[i]] = b[i];
    Build(1, 1, N);
    while(M--) {
        LL opt = read();
        if(opt == 1) {
            LL x = read(), val = read();
            IntervalAdd(1, ID[x], ID[x] + siz[x] - 1, val);	
        }
        else if(opt == 2) {
            LL x = read(), y = read(), val = read();
            TreeAdd(x, y, val);
        }
        else if(opt == 3) {
            LL x = read(), y = read();
            LL val = TreeSum(x, y, 0) % mod; 
            val = (val * val) % mod; val = (val - TreeSum(x, y, 1) + mod) % mod;
            printf("%lld\n", 1ll * val * inv % mod);         	
        }
    }
    return 0;
}