牛客算法周周练15 D 树上求和
树上求和
https://ac.nowcoder.com/acm/contest/6290/D
D 树上求和
题目地址：
基本思路：
比较裸的一道题，没有什么思维量，
首先要维护子树状态，很明显我们可以求个序，然后用数据结构去维护，
观察一下题意，要维护区间平方和，进行区间查询和区间修改，所以考虑线段树。
那么维护区间平方和的线段树怎么写函数,其实也比较简单,
假设这段区间内的平方和开始为
,
那么我们将整个区间加,就变为
化简一下提出来其实就是
所以我们在维护区间平方和的同时在维护一下那部分普通的区间和，然后就很容易进行了。
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
const int mod = 23333;
int n,q;
struct edge {
int next, v;
}edges[maxn << 1];
int cnt,tot,w[maxn];
int head[maxn];
void init() {
memset(head, -1, sizeof(head));
cnt = 0; tot = 0;
}
void add_edge(int u,int v) {
edges[cnt].next = head[u];
edges[cnt].v = v;
head[u] = cnt++;
}
int L[maxn],R[maxn],dfn[maxn];
void dfs(int u,int ***] = ++tot;
dfn[tot] = u;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (v == fa) continue;
dfs(v, u);
}
R[u] = tot;
}
struct node{
int l,r,sum,res,add;
}t[maxn<<2];
inline void push_up(int p) {
t[p].res = (t[p << 1].res + t[p << 1 | 1].res) % mod;
t[p].sum = (t[p << 1].sum + t[p << 1 | 1].sum) % mod;
}
inline void push_down(int p) {
if (t[p].add) {
int v = t[p].add; t[p].add = 0;
t[p << 1].add = (t[p << 1].add + v) % mod;
t[p << 1 | 1].add = (t[p << 1 | 1].add + v) % mod;
int ll = t[p << 1].r - t[p << 1].l + 1;
int lr = t[p << 1 | 1].r - t[p << 1 | 1].l + 1;
t[p << 1].res = (t[p << 1].res + ll * v * v % mod + 2 * t[p << 1].sum * v % mod) % mod;
t[p << 1 | 1].res = (t[p << 1 | 1].res + lr * v * v % mod + 2 * t[p << 1 | 1].sum * v % mod) % mod;
t[p << 1].sum = (t[p << 1].sum + ll * v) % mod;
t[p << 1 | 1].sum = (t[p << 1 | 1].sum + lr * v) % mod;
}
}
void build(int p,int l,int r) {
t[p].l = l; t[p].r = r;
if (l == r) {
t[p].sum = w[dfn[l]];
t[p].res = t[p].sum * t[p].sum % mod;
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
push_up(p);
}
void change(int p,int l,int r,int v) {
if (t[p].l == l && t[p].r == r) {
t[p].res = (t[p].res + (r - l + 1) * v * v % mod + 2 * t[p].sum * v % mod) % mod;
t[p].sum = (t[p].sum + (r - l + 1) * v % mod) % mod;
t[p].add = (t[p].add + v) % mod;
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid) change(p << 1, l, r, v);
else if (l > mid) change(p << 1 | 1, l, r, v);
else change(p << 1, l, mid, v), change(p << 1 | 1, mid + 1, r, v);
push_up(p);
}
int ask(int p,int l,int r) {
if (t[p].l == l && t[p].r == r) return t[p].res % mod;
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid) return ask(p << 1, l, r);
else if (l > mid) return ask(p << 1 | 1, l, r);
else return (ask(p << 1, l, mid) + ask(p << 1 | 1, mid + 1, r)) % mod;
}
signed main() {
n = read(),q = read();
rep(i,1,n) w[i] = read();
init();
rep(i,1,n-1) {
int u = read(), v = read();
add_edge(u, v);
add_edge(v, u);
}
dfs(1,0);
build(1,1,n);
while (q--){
int op = read();
if(op == 1){
int x = read(),y = read();
change(1,L[x],R[x],y);
}else{
int x = read();
int ans = ask(1,L[x],R[x]);
print(ans);
puts("");
}
}
return 0;
}
投递百度等公司10个岗位 >
