一棵点带权的有根树, 要求支持: - 单点加 - 子树加 - 查询以u为lca的不同两点的点权之和的期望
(1≤节点数,操作数≤3*10^5, 0≤|权值|,|加数|≤2*10^4) 设
推一推式子:
分母可以预处理, 但这是什么东西??
先只看单点加这种修改. 如果直接维护答案, 可以树链剖分, 但一个点有很多儿子, 乘上哪个系数呢? 弄成子树求和的形式呢? 也不行啊......
瞥了一眼题解. 既然都已经树链剖分了......每个点可以有很多儿子, 但只能有一个重儿子啊.
预处理分母, 和分子的原始值. 维护分子的变化量. 不妨将轻重子树的贡献分开考虑. 树链剖分.
- 单点加 首先计算点
对自己的影响, 然后考虑对祖先的影响. 由于 到根的路径上只有 条轻边, 可以对轻子树的贡献暴力. 树状数组+DFS序实现子树求和, 重子树的权值和在树状数组里查询. - 子树加 对祖先的影响和单点加一样. 树状数组需要支持区间加和区间查询. 子树中, 每个点
的分子除去重子树的贡献, 还加上了 , 即 乘一个系数. 系数可以预处理出来. 再来一个树状数组记录 即可. - 查询 分子为四部分之和: 原始值, 轻子树(暴力), 轻子树(子树加), 重子树.
子树加会使子树内所有点的答案增加
时间复杂度
轻重子树的贡献分开考虑, 以前没想过......看来树链剖分的姿势水平有待提高.
typedef long long ll;
const int N = 3e5 + 1;
int n;
struct BIT
{
ll v[N];
void add(int i, ll d)
{
while (i <= n)
v[i] += d, i += i&-i;
}
ll ask(int i)
{
ll s = 0;
while (i)
s += v[i], i -= i&-i;
return s;
}
} C;
struct BIT2
{
BIT A, B;
void add(int i, ll d)
{
A.add(i, i*d);
B.add(i, d);
}
ll ask(int i)
{
return B.ask(i)*(i+1) - A.ask(i);
}
} T;
vector<int> adj[N];
int dfs_clock, fa[N], dfn[N], sz[N], mx[N], w[N], top[N];
ll deno[N], base[N], sum[N], c[N];
void dfs_1(int u)
{
sz[u] = 1;
sum[u] = w[u];
rep (i, 0, adj[u].size())
{
int v = adj[u][i];
dfs_1(v);
sz[u] += sz[v];
sum[u] += sum[v];
if (sz[v] > sz[mx[u]]) mx[u] = v;
}
base[u] = 1LL * w[u] * (sz[u]-1);
deno[u] = 1LL * sz[u] * sz[u] - 1;
rep (i, 0, adj[u].size())
{
int v = adj[u][i];
base[u] += (sz[u]-sz[v]) * sum[v];
deno[u] -= 1LL * sz[v] * sz[v];
}
deno[u] /= 2;
}
void dfs_2(int u, int t)
{
dfn[u] = ++dfs_clock;
top[u] = t;
c[u] = sz[u] - 1;
if (mx[u]) dfs_2(mx[u], t);
rep (i, 0, adj[u].size())
{
int v = adj[u][i];
if (v != mx[u]) c[u] += 1LL * sz[v] * (sz[u]-sz[v]), dfs_2(v, v);
}
}
void add_chain(int x, ll d)
{
if (x == mx[fa[x]]) x = top[x];
while (x != 1)
base[fa[x]] += d * (sz[fa[x]]-sz[x]), x = top[fa[x]];
}
inline double query(int x)
{
int y = mx[x];
ll b = base[x] + c[x] * C.ask(dfn[x])
+ (sz[x]-sz[y]) * (T.ask(dfn[y]+sz[y]-1)-T.ask(dfn[y]-1));
return (double)b/deno[x];
}
int main()
{
int m;
scanf("%d%d", &n, &m);
rep (i, 2, n+1)
{
scanf("%d", fa+i);
adj[fa[i]].push_back(i);
}
rep (i, 1, n+1) scanf("%d", w+i);
dfs_1(1);
dfs_2(1, 1);
while (m--)
{
char o;
int u;
ll d;
scanf(" %c%d", &o, &u);
if (o == 'Q')
{
printf("%.6f\n", query(u));
}
else
{
scanf("%lld", &d);
if (o == 'S')
{
base[u] += d * (sz[u]-1);
add_chain(u, d);
T.add(dfn[u], d);
T.add(dfn[u]+1, -d);
}
else
{
add_chain(u, sz[u] * d);
C.add(dfn[u], d);
C.add(dfn[u]+sz[u], -d);
T.add(dfn[u], d);
T.add(dfn[u]+sz[u], -d);
}
}
}
return 0;
}