首页 > 代码库 > bzoj3683 Falsita
bzoj3683 Falsita
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3683
【题解】
首先我们需要化简式子
$ans = P / S$
其中，$S = (sz_x^2 - 1 - \sum_{y = son[x]} sz_y^2) / 2$
这个显然可以预处理。
然后我们经过简单推导可以得出$ P = w_x * (sz_x - 1) + \sum_{y = son[x]} (sz_x - sz_y) * sum_y$
经过如下化简，可以得到
$ P = w_x * sz_x - w_x + \sum_{y = son[x]} (sz_x * sum_y - sz_y * sum_y)$
$ P = w_x * sz_x - w_x + sz_x * (sum_x - w_x) - \sum_{y = son[x]} sz_y * sum_y$
$ P = sz_x * sum_x - w_x - \sum_{y = son[x]} sz_y * sum_y$
然后我们可以树链剖分，每次查询一个点，可以把这个点的信息和重儿子的信息直接查询出来。
然后如果某个轻儿子的整棵子树有一个累加值$\Delta$，那么经过上面推导容易得到整个需要加的系数为$\sum_{y = son[x], y\not= mx[x]} sz_y * sz_y$
系数预处理出来，就可以算答案了。
如果某棵轻儿子的下面某个子树修改了，就从修改的那个点暴力往上跳更新答案，因为这时候不是整棵子树的修改。
暴力更改答案的贡献可以算出来是$sz_y * \Delta$，$y$表示当前的这个点。
每个轻儿子的答案需要在他们的父亲位置进行存储（我们询问是询问父亲的）
然后维护两个树状数组，一个维护每个点加的$\Delta$，一个维护每个子树整体加的$\Delta$，这个是作为轻链计算答案用的。
然后写起来还可以吧？感谢chrt教我这题（逃
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 4e5 + 10, M = 8e5 + 10; const int mod = 1e9+7; struct BIT { int n; ll c[N]; # define lb(x) (x & (-x)) inline void set(int _n) { n = _n; memset(c, 0, sizeof c); } inline void edt(int x, ll d) { for (; x<=n; x+=lb(x)) c[x] += d; } inline ll sum(int x) { ll ret = 0; for (; x; x-=lb(x)) ret += c[x]; return ret; } }; struct BIT2 { BIT a, b; inline void set(int n) { a.set(n); b.set(n); } inline void edt(int x, int y, ll d) { a.edt(x, d); a.edt(y+1, -d); b.edt(x, d*x); b.edt(y+1, -d*(y+1)); } inline ll sum(int x) { return a.sum(x) * (x+1) - b.sum(x); } inline ll sum(int x, int y) { if(x > y) return 0ll; return sum(y) - sum(x-1); } }T, C; int n, w[N], par[N]; int head[N], nxt[N], to[N], tot = 0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } int sz[N], dfn[N], ed[N], DFN, mx[N], top[N]; ll fm[N], fz[N], sum[N], c[N]; inline void dfs(int x) { int mxsz = 0, mxid = 0; sz[x] = 1; fm[x] = -1; sum[x] = w[x]; for (int i=head[x]; i; i=nxt[i]) { dfs(to[i]); if(sz[to[i]] > mxsz) mxsz = sz[to[i]], mxid = to[i]; sz[x] += sz[to[i]]; sum[x] += sum[to[i]]; fm[x] -= 1ll * sz[to[i]] * sz[to[i]]; } mx[x] = mxid; fm[x] += 1ll * sz[x] * sz[x]; fm[x] /= 2; } inline void dfstop(int x, int tp) { dfn[x] = ++DFN; top[x] = tp; fz[x] = sum[x] * sz[x] - w[x]; c[x] = 0; if(mx[x]) dfstop(mx[x], tp); for (int i=head[x]; i; i=nxt[i]) if(to[i] != mx[x]) { dfstop(to[i], to[i]); c[x] += 1ll * sz[to[i]] * sz[to[i]]; fz[x] -= sum[to[i]] * sz[to[i]]; } ed[x] = DFN; } inline void jump(int x, ll d) { int y; while((y = top[x]) != 1) { fz[par[y]] -= 1ll * sz[y] * d; y = par[y]; x = y; } } int main() { int Q; cin >> n >> Q; T.set(n); C.set(n); for (int i=2; i<=n; ++i) scanf("%d", par+i), add(par[i], i); for (int i=1; i<=n; ++i) scanf("%d", w+i); dfs(1); dfstop(1, 1); char op[23]; int x, d; while(Q--) { // for (int i=1; i<=n; ++i) cout << T.sum(dfn[i], dfn[i]) << endl; scanf("%s%d", op, &x); if(op[0] == ‘S‘) { scanf("%d", &d); jump(x, d); T.edt(dfn[x], dfn[x], d); } else if(op[0] == ‘M‘) { scanf("%d", &d); jump(x, 1ll * d * sz[x]); T.edt(dfn[x], ed[x], d); C.edt(dfn[x], ed[x], d); } else { int y = mx[x]; ll tem = fz[x] + T.sum(dfn[x], ed[x]) * sz[x] - T.sum(dfn[x], dfn[x]) - (sum[y] + T.sum(dfn[y], ed[y])) * sz[y] - c[x] * C.sum(dfn[x], dfn[x]); ld ans = (ld)tem / (ld)fm[x]; printf("%.6lf\n", (double)ans); } } return 0; } /* 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 2 */
bzoj3683 Falsita