Gardener Bo (树剖 + 问题分解)

一开始没看懂计算答案的第四部和update2,很迷。然后一直推敲之后才发下我计算的时候漏掉一个关键点。没有把加值的影响放到父节点上。

#include<bits/stdc++.h>
#define M ((l + r) / 2)
#define ls (rt << 1)
#define rs ((rt << 1) | 1)
#define UI unsigned int
using namespace std; const int maxn = 6e5 + ;
vector<int>Gra[maxn];
UI f[maxn], c[maxn], sz[maxn], w[maxn], sum[maxn << ], add[maxn], cntSon[maxn], cntSeson[maxn];
int fa[maxn], N, top[maxn], hSon[maxn];
int edn[maxn], stn[maxn]; /**
stn dfs序的起点, edn dfs序的终点,hSon 重树,add 加重, cntSon 直接子节点数量
sz 树的总大小, cntSeson 2层子节点的总数量, c 子树重复计算个数,
f 未进行操作的子树总值 top 重链的父节点。
**/ ///主要是计算初始值
void dfs1(int u) {
cntSeson[u] = cntSon[u] = hSon[u] = c[u] =;
sz[u] = ;
for(auto v: Gra[u]) {
if(v == fa[u]) continue;
dfs1(v);
sz[u] += sz[v];
cntSon[u] ++;
cntSeson[u] += cntSon[v] + ;
c[u] += sz[v] * cntSon[v];
if(sz[hSon[u]] < sz[v]) hSon[u] = v;
}
f[u] = w[u] * (sz[u] + );
for(auto v: Gra[u]) {
if(v == fa[u]) continue;
f[u] += (sz[u] - sz[v]) * w[v];
w[u] += w[v];
}
} ///dfs序,以及最重要的重树父节点
void dfs2(int u, int t) {
top[u] = t;
stn[u] = ++N;
if(hSon[u]) dfs2(hSon[u], t);
for(auto v: Gra[u]) {
if(v == fa[u] || hSon[u] == v) continue;
dfs2(v, v);
}
edn[u] = N;
} ///查询线段树上的价值
int query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) return sum[rt];
int ret = ;
if(M >= L) ret += query(L, R, l, M, ls);
if(M < R) ret += query(L, R, M + , r, rs);
return ret;
} ///作用之后对父节点的影响
void update1(int x, int val) {
while(top[x] != top[]) {
int v = top[x], u = fa[v];
f[u] += (sz[u] - sz[v]) * val;
x = u;
}
} ///存加的价值的影响范围
void update2(int p, UI val, int l, int r, int rt) {
sum[rt] += val;
if(l == r) return ;
if(M >= p) update2(p, val, l, M, ls);
else update2(p, val, M + , r, rs);
} int main() {
freopen("data.txt", "r", stdin);
int n, m, st, ed;
while(~scanf("%d%d", &n, &m)) {
memset(add, , sizeof(add));
memset(sum, , sizeof(sum));
N = ;
for(int i = ; i <= n; i ++)
Gra[i].clear();
for(int i = ; i <= n; i ++) {
scanf("%d", &ed);
fa[i] = ed;
Gra[ed].push_back(i);
Gra[i].push_back(ed);
}
for(int i = ; i <= n; i ++)
scanf("%u", &w[i]);
dfs1();
dfs2(, );
while(m -- ) {
int op, u;
UI x;
scanf("%d", &op);
if(op == ) {
scanf("%d%u", &u, &x);
add[u] += x;
///沿着重树往上预计算重树点价值的作用,之后就不用重复计算这一部分了,这样重树这里就可以成为一个撬棍
update1(u, x * ( + cntSeson[u]));
///将每个点的填加的价值放进去线段树
update2(stn[u], x * (cntSeson[u]+ ), , n, );
} else {
scanf("%d", &u);
UI ans = f[u];
///加值时作用在当前节点上的情况
ans += add[u] * ( + sz[u] * cntSeson[u] - c[u]);
if(fa[u])///加值时作用在子节点上的情况
ans += add[fa[u]] * ( + sz[u] * cntSon[u]);
if(fa[fa[u]])///加值时作用在孙子节点上的情况
ans += add[fa[fa[u]]] * ( + sz[u]);
if(hSon[u])///计算除重树内加值的价值,因为已经在update1计算过了到f中了
ans += (sz[u] - sz[hSon[u]]) * query(stn[hSon[u]], edn[hSon[u]], , n, );
printf("%u\n",ans);
}
}
}
return ;
}
上一篇:后记:IT软件人员学习的书籍 - IT软件人员书籍系列文章


下一篇:Android调用系统的发邮件功能