[BZOJ3683]Falsita 题解
![[BZOJ3683]Falsita 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180704a.jpg "180704a")
题目地址：BZOJ：Problem 3683. — Falsita
题目描述
描述
到海边了呢……
如果没有那次选择,现在是不是会好些呢……
都过去了。
仰望着星空,迎面吹过一阵阵海风,倚靠着护栏,Fine 在海边静静地伫立着,在一个个无际的长夜后,Fine 终于放下了往事的痛楚,得到了治愈。
但是作为 Fine 的另一重人格的 Falsita 就没那么幸运了。她仍然被各种繁忙的事务困扰着。
虽然同在一副躯体中,Fine 与 Falsita 的精神世界却相差甚远,Fine 可以轻易地构造出幻梦时,Falsita 却只能停留在现实的痛楚中。
但是为了生活需要,她们还是需要经常达成共识。
让我们形式化的描述一下吧。
她们所在的精神世界是一棵以 1 号节点为根的树,每个树上的节点 u 都有一个权值Wu,她们每个人分别都在一个节点上,达成共识的方法就是两个人都到达一个共识节点(即到达它们的最近公共祖先)。
一个点 u 与另外一个点 v 之间想要达到共识需要花费的代价为Wu+Wv。
有时两人的精神有所触动时,有时点的权值会改变成某个数,有时以某个点的子树中的所有点的权值会加上某个数。
Falsita 和 Fine 经常需要达成共识,每一次询问,已知达成的共识节点,求她们花费的期望代价。
题意简述
有一棵有点权的树，以1为根。有三种操作：
- 单点点权加一个数
- 子树点权加一个数
- 求随机从$u$子树中选择两个点$(i, j)$且它们的LCA为$u$，$w_i+w_j$的期望
输入输出格式
输入格式：
输入共 m + 3 行。
第一行两个整数 n, m ,表示节点个数和操作数。
第二行 n – 1 个整数Pi,表示节点 i ( i = 2 . . . n ) 的父亲节点的编号。
第三行 n 个整数Wi。
接下来 m 行,每行表示一个操作。
1. S u delta 表示将节点 u 的权值加上 delta 。
2. M u delta 表示将以节点 u 为根的子树中的所有节点的权值加上 delta。
3. Q u 表示询问共识节点为 u 时的答案。
询问保证 u 不是叶子节点。
输出格式：
对于每组询问,输出答案,答案精确到小数点后 6 位。
你的程序输出的答案需要与标准答案之差不超过10^(-5)。
输入输出样例
输入样例#1：
4 6 1 2 2 0 -6 3 0 S 2 -5 M 3 8 S 1 -1 M 4 7 M 3 2 Q 1
输出样例#1：
2.000000
说明
前5个操作后，四个节点的权值分别为-1,-11,13,7。最近公共祖先为1的点对有(1,2),(1,3),(1,4)，权值和分别为-12,12,6，故答案为(-12+12+6)/3=2。
对于 100% 的数据,1 ≤ n, m ≤ 300000, 0≤ |delta|, |Wi|≤ 20000。
题解
首先，期望可以表示为所有可能情况的和/情况数。对于确定的点$u$，它子树中所有可能情况的数量是可以预处理出来的。这个答案就是$u$子树中不同时在$u$的某个儿子的子树内的点对数，我们可以DFS树的使用利用子树大小来计算，假如计算$u$的方案数，$u$有儿子$v$，在遍历到$v$的时候，只需要对方案数加上$siz[v] \cdot (已经遍历过的子树大小和+1)$即可。
接下来考虑期望中分子的问题。如果不带修改，我们可以DFS的时候计算出所有节点的答案。如果用$sum[u]$表示$u$子树内所有节点的权值和，那么$u$有儿子$v$，$v$子树对$u$的答案贡献是$sum[v] \cdot (siz[u] – siz[v])$。
接下来我们考虑修改的问题，单点修改时，对该点答案的影响是$delta \cdot (siz[u] – 1)$，若该点有祖先$anc$，该点到该祖先路径上，祖先的儿子节点是$anc’$，那么对于该点的该祖先的影响是$delta \cdot (siz[anc] – siz[anc’])$。我们考虑进行树剖，在线段树上来维护这些个影响。显然，我们可以维护一个标记$delta \cdot (siz[u] – siz[v])$，其中$v$是$u$在重链上的儿子，这样，单点修改$u$就可以从$u$的父亲开始跳重链改了。但是当我们发现，一条重链最深的节点的重儿子可能不是修改点到根路径上该点的儿子，因此最深节点的情况要特别处理。我们直接把这个特别处理的修改改到该点处就好了。
对于子树加的情况，我们发现，只需要对子树里所有的节点的分子加上$delta \cdot 分母$就好了。而对于子树根的祖先们，其实跟单点修改产生的影响相同，只不过这里的影响是$delta \cdot siz[u]$。
总之，我们树剖以后在线段树上把这些个标记维护好就能实现正确的复杂度$O(n \log^2 n)$。
代码
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
inline bool isop(char c) {
return c == 'S' || c == 'M' || c == 'Q';
}
inline char readop() {
char c;
while(!isop(c = fgc())) {}
return c;
}
const int MAXN = 300005;
int n, m, w[MAXN];
std::vector<int> gra[MAXN];
int fa[MAXN], siz[MAXN], dep[MAXN], son[MAXN], dfn[MAXN], vn[MAXN], top[MAXN], clk;
LL ans1[MAXN], ans2[MAXN], sum[MAXN];
inline void dfs1(int u) {
siz[u] = 1; sum[u] = w[u];
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u]) continue;
fa[v] = u; dep[v] = dep[u] + 1;
dfs1(v);
ans2[u] += 1ll * siz[v] * siz[u];
siz[u] += siz[v];
sum[u] += sum[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
dfn[u] = ++clk; vn[dfn[u]] = u; top[u] = tp;
ans1[u] += 1ll * w[u] * (siz[u] - 1);
if(son[u]) {
ans1[u] += 1ll * (siz[u] - siz[son[u]]) * sum[son[u]];
dfs2(son[u], tp);
}
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u] || v == son[u]) continue;
ans1[u] += 1ll * (siz[u] - siz[v]) * sum[v];
dfs2(v, v);
}
}
#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
LL tag1[MAXN << 2], tag2[MAXN << 2];
// 1: ptadd 2: subtadd
inline void pushdown(int o, int l, int r) {
if(tag1[o]) {
tag1[lch] += tag1[o]; tag1[rch] += tag1[o];
if(l == mid) ans1[vn[l]] += tag1[o] * ans2[vn[l]];
if(mid + 1 == r) ans1[vn[r]] += tag1[o] * ans2[vn[r]];
tag1[o] = 0;
}
if(tag2[o]) {
tag2[lch] += tag2[o]; tag2[rch] += tag2[o];
if(l == mid) ans1[vn[l]] += (siz[vn[l]] - siz[son[vn[l]]]) * tag2[o];
if(mid + 1 == r) ans1[vn[r]] += (siz[vn[r]] - siz[son[vn[r]]]) * tag2[o];
tag2[o] = 0;
}
}
inline void modify(int o, int l, int r, int ll, int rr, LL v, int type) {
if(l >= ll && r <= rr) {
if(type == 1) {
if(l == r) ans1[vn[l]] += v * ans2[vn[l]];
else tag1[o] += v;
} else if(type == 2) {
if(l == r) ans1[vn[l]] += (siz[vn[l]] - siz[son[vn[l]]]) * v;
else tag2[o] += v;
}
return;
}
pushdown(o, l, r);
if(ll <= mid) modify(lch, l, mid, ll, rr, v, type);
if(rr > mid) modify(rch, mid + 1, r, ll, rr, v, type);
}
inline void update(int o, int l, int r, int x) {
if(l == r) return;
pushdown(o, l, r);
if(x <= mid) update(lch, l, mid, x);
else update(rch, mid + 1, r, x);
}
inline void modify(int u, int _lu, LL v) {
int tu = top[u], lu = _lu;
while(u) {
if(dfn[tu] != dfn[u]) modify(1, 1, n, dfn[tu], dfn[u] - 1, v, 2);
ans1[u] += v * (siz[u] - siz[lu]);
lu = u; u = fa[tu]; tu = top[u];
}
}
int main() {
n = readint(); m = readint();
for(int i = 2, p; i <= n; i++) {
p = readint();
gra[i].push_back(p); gra[p].push_back(i);
}
for(int i = 1; i <= n; i++) {
w[i] = readint();
}
dfs1(1);
dfs2(1, 1);
char op; int u, delta;
while(m--) {
op = readop(); u = readint();
if(op != 'Q') delta = readint();
if(op == 'S') {
ans1[u] += 1ll * delta * (siz[u] - 1);
modify(fa[u], u, delta);
} else if(op == 'M') {
modify(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, delta * 2ll, 1);
modify(fa[u], u, 1ll * delta * siz[u]);
} else {
update(1, 1, n, dfn[u]);
printf("%.6lf\n", double(ans1[u]) / ans2[u]);
}
}
return 0;
}
