题目描述
一棵 $n$ 个点的树,执行 $m$ 次操作
$1.$ 路径赋值
$2.$ 路径累加
$3.$ 路径累乘
$4.$ 路径求三次方和
$n \leq 100000$ , $m \leq 10000$
树链剖分/线段树
显然树剖&线段树可以做
最复杂的地方在于如何在线段树上维护三次方和
下面用 $sumk$ 表示修改操作之前的区间的 $k$ 次方和
$len$ 表示区间长度,$w$ 表示修改操作之前的点权,$c$ 表示操作权值
$newk$ 表示修改之后的区间的 $k$ 次方和
- 区间赋值
$new3$
$ = len \cdot {c}^{3}$
- 区间累乘
$new3$
$ = \sum {(w \cdot c)}^{3}$
$ = \sum {w}^{3} \cdot {c}^{3}$
$ = {c}^{3} \sum {w}^{3}$
$ = {c}^{3} \cdot sum3$
- 区间累加
$new3$
$ = \sum {(w + c)}^{3}$
$ = \sum {w}^{3} + 3{w}^{2}c + 3w{c}^{2} + {c}^{3}$
$ = sum3 + 3 \cdot sum2 \cdot c + 3 \cdot sum1 \cdot {c}^{2} + len \cdot {c}^{3}$
$new2$
$ = \sum {(w + c)}^{2}$
$ = \sum {w}^{2} + 2wc + {c}^{2}$
$ = sum2 + 2 \cdot sum1 \cdot c + len \cdot {c}^{2}$
$new1$
$ = \sum w + c$
$ = sum1 + len \cdot c$
时间复杂度 $O(mlog^2n)$
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 100010, M = N << 1, mod = 1e9 + 7;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int n, m;
int w[N];
int sz[N], dep[N], son[N], f[N];
void dfs(int u, int fa)
{
sz[u] = 1, dep[u] = dep[fa] + 1, son[u] = 0, f[u] = fa;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, u);
sz[u] += sz[j];
if(sz[j] > sz[son[u]]) son[u] = j;
}
}
int id[N], rk[N], top[N], tot;
void dfs2(int u, int t)
{
id[u] = ++ tot, rk[tot] = u, top[u] = t;
if(son[u]) dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == f[u] or j == son[u]) continue;
dfs2(j, j);
}
}
struct Node{
int l, r;
int lazy, add, mul;
int sum, sum2, sum3;
}tr[N << 2];
void pushup(int u)
{
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
tr[u].sum2 = (tr[u << 1].sum2 + tr[u << 1 | 1].sum2) % mod;
tr[u].sum3 = (tr[u << 1].sum3 + tr[u << 1 | 1].sum3) % mod;
}
void build(int u, int l, int r)
{
tr[u] = {l, r, -1, 0, 1};
if(l == r)
{
int c = w[rk[l]];
tr[u].sum = c;
tr[u].sum2 = (LL)c * c % mod;
tr[u].sum3 = (LL)tr[u].sum2 * c % mod;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void cover(int u, int w) // 区间赋值
{
int len = tr[u].r - tr[u].l + 1;
tr[u].sum = (LL)len * w % mod;
tr[u].sum2 = (LL)len * w % mod * w % mod;
tr[u].sum3 = (LL)len * w % mod * w % mod * w % mod;
tr[u].lazy = w;
tr[u].add = 0;
tr[u].mul = 1;
}
void eval(int u, int add, int mul) // 区间加/乘
{
int len = tr[u].r - tr[u].l + 1;
if(mul != 1)
{
tr[u].sum = (LL)tr[u].sum * mul % mod;
tr[u].sum2 = (LL)tr[u].sum2 * mul % mod * mul % mod;
tr[u].sum3 = (LL)tr[u].sum3 * mul % mod * mul % mod * mul % mod;
}
if(add)
{
tr[u].sum3 = (tr[u].sum3 + 3ll * tr[u].sum2 * add + 3ll * tr[u].sum * add % mod * add + (LL)add * add % mod * add % mod * len) % mod;
tr[u].sum2 = (tr[u].sum2 + 2ll * tr[u].sum * add + (LL)add * add % mod * len) % mod;
tr[u].sum = (tr[u].sum + (LL)add * len) % mod;
}
tr[u].mul = (LL)tr[u].mul * mul % mod;
tr[u].add = ((LL)tr[u].add * mul + add) % mod;
}
void pushdown(int u)
{
if(tr[u].lazy != -1)
{
cover(u << 1, tr[u].lazy);
cover(u << 1 | 1, tr[u].lazy);
tr[u].lazy = -1;
}
eval(u << 1, tr[u].add, tr[u].mul);
eval(u << 1 | 1, tr[u].add, tr[u].mul);
tr[u].add = 0;
tr[u].mul = 1;
}
void modify(int u, int l, int r, int op, int w)
{
if(tr[u].l >= l and tr[u].r <= r)
{
if(op == 1) cover(u, w);
else
{
int add = 0, mul = 1;
if(op == 2) add = w;
else mul = w;
eval(u, add, mul);
}
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, op, w);
if(r > mid) modify(u << 1 | 1, l, r, op, w);
pushup(u);
}
int query(int u, int l, int r)
{
if(tr[u].l >= l and tr[u].r <= r) return tr[u].sum3;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if(l <= mid) res = query(u << 1, l, r);
if(r > mid) res = (res + query(u << 1 | 1, l, r)) % mod;
return res;
}
void update(int a, int b, int op, int w)
{
while(top[a] != top[b])
{
if(dep[top[a]] < dep[top[b]]) swap(a, b);
modify(1, id[top[a]], id[a], op, w);
a = f[top[a]];
}
if(id[a] > id[b]) swap(a, b);
modify(1, id[a], id[b], op, w);
}
int ask(int a, int b)
{
int res = 0;
while(top[a] != top[b])
{
if(dep[top[a]] < dep[top[b]]) swap(a, b);
res = (res + query(1, id[top[a]], id[a])) % mod;
a = f[top[a]];
}
if(id[a] > id[b]) swap(a, b);
return (res + query(1, id[a], id[b])) % mod;
}
int main()
{
int _;
scanf("%d", &_);
for(int T = 1; T <= _; T ++)
{
printf("Case #%d:\n", T);
memset(h, -1, sizeof h);
idx = tot = 0;
scanf("%d", &n);
for(int i = 1; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
dfs(1, 0);
dfs2(1, 1);
build(1, 1, n);
scanf("%d", &m);
while(m --)
{
int op, a, b, c;
scanf("%d%d%d", &op, &a, &b);
if(op <= 3)
{
scanf("%d", &c);
update(a, b, op, c);
}
else
printf("%d\n", ask(a, b));
}
}
return 0;
}