LOJ #2434. 「ZJOI2018」历史(LCT)

时间:2021-07-13 21:52:02

题意

click here

题解

我们首先考虑答案是个什么样的东西, 不难 发现每个点可以单独计算它的贡献。

令每个点 \(i\) 崛起次数为 \(a_i\) 。

假设一个点子树的 \(\sum a_i\) 分别为 \(b_1,b_2,\dots,b_k\) ,令 \(S = a_i + \sum b_j\) 。

那么这个点的答案为

\[\min (2(S - \max(\max\{b_j\}, a_i)), S - 1)
\]

至于为什么是这样可以简单说明下:

\(S - 1\) :显然是这个点的答案的上界,除了第一次,后面每一次最多对这个点贡献一次。

\(2(S - \max(\max\{b_j\}, a_i))\) :不难发现,我们总可以找到一种方案使得 \(S - \max\) 那种与 剩下的 \(\max(\max\{b_j\}, a_i)\) 交错出现,使得这个答案取得上界,然后每次会存在两种贡献。

这样我们就可以得到一个 \(O(n)\) 的 \(dp\) 了。


我们考虑如何动态维护这个 \(dp\) 。

不难发现这个操作及其类似于 Link_Cut_Tree 中的 Access 操作。

我们令 \(b_u = \sum_{v \in child(u)} a_v\) 也就是 \(u\) 的子树 \(a\) 和。

我们考虑维护这个东西,不难发现每次给一个点的 \(a_u\) 加上 \(v\) ,相当于把这个点到根的 \(b_u\) 加上 \(v\) 。

然后考虑如何维护一个点的贡献,如果 \(u\) 存在一个儿子 \(v\) 使得 \(b_v \times 2 > b_u + 1\) 那么我们定义 \(v \to u\) 为实边。

其余的边都为虚边。不难发现这些实边会对于 \(u\) 存在 \(2(b_u - b_v)\) 的贡献。( \(a\) 不可能存在贡献,因为 \(b_v\) 已经占据一半了)

然后虚边的贡献就是 \(\min(b_u - 1, 2(b_u - a_u))\) 。

这个可以自己列列不等式,讨论讨论就行了。

然后我们每次 Access 操作就是将链上的一些点加权,并且更换虚实边就行了,重新计算贡献就行了。

这个直接用支持加法标记的 LCT 维护就行了。

不难发现一个点到根的实边最多是 \(\log w\) 条,因为每条实边会使得权值至少翻倍。

所以最后复杂度就是 \(O(n + q\log w)\) 的。

总结

有些题,我们先找出它的一些巧妙性质以及结论,然后考虑用数据结构维护。(这似乎也是出题的好思路?)

代码

不太会写的话还是建议看看代码的。。

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll;
inline bool chkmin(ll &a, ll b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(ll &a, ll b) {return b > a ? a = b, 1 : 0;} inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * fh;
} void File() {
#ifdef zjp_shadow
freopen ("374.in", "r", stdin);
freopen ("374.out", "w", stdout);
#endif
} const int N = 4e5 + 1e3; int n, m;
vector<int> G[N]; int son[N]; ll Ans, ans[N], b[N], a[N];
inline void ReCalc(int u) {
Ans -= ans[u];
ans[u] = son[u] ? 2 * (b[u] - b[son[u]]) : b[u] - 1;
if (a[u] * 2 > b[u] + 1) ans[u] = 2 * (b[u] - a[u]);
Ans += ans[u];
} #define ls(o) ch[o][0]
#define rs(o) ch[o][1] namespace Link_Cut_Tree { int ch[N][2], fa[N]; inline bool get(int o) { return o == rs(fa[o]); } inline bool is_root(int o) { return o != ls(fa[o]) && o != rs(fa[o]); } inline void Rotate(int v) {
int u = fa[v], t = fa[u], d = get(v);
fa[ch[u][d] = ch[v][d ^ 1]] = u;
fa[v] = t; if (!is_root(u)) ch[t][rs(t) == u] = v;
fa[ch[v][d ^ 1] = u] = v;
} ll tag[N];
inline void Add(int o, ll uv) { if (o) b[o] += uv, tag[o] += uv; } inline void Push_Down(int o) {
if (!tag[o]) return ;
Add(ls(o), tag[o]);
Add(rs(o), tag[o]); tag[o] = 0;
} inline void Push_All(int o) {
if (!is_root(o)) Push_All(fa[o]); Push_Down(o);
} inline void Splay(int o) {
Push_All(o);
for (; !is_root(o); Rotate(o))
if (!is_root(fa[o])) Rotate(get(o) != get(fa[o]) ? o : fa[o]);
} inline int Get_Root(int o) {
while (ls(o)) Push_Down(o), o = ls(o); return o;
} inline void Access(int o, int uv) {
for (int t = 0; o; o = fa[t = o]) {
Splay(o);
b[o] += uv; Add(ls(o), uv); if (son[o]) {
Push_All(son[o]);
if (b[son[o]] * 2 <= b[o] + 1) son[o] = rs(o) = 0;
}
int to = Get_Root(t);
if (b[to] * 2 > b[o] + 1) son[o] = to, rs(o) = t;
ReCalc(o);
}
} } void Dfs_Init(int u, int fa = 0) {
Link_Cut_Tree :: fa[u] = fa; b[u] = a[u]; int to = 0;
for (int v : G[u]) if (v != fa) {
Dfs_Init(v, u); b[u] += b[v];
if (b[v] > b[to]) to = v;
}
if (b[to] * 2 > b[u]) son[u] = Link_Cut_Tree :: rs(u) = to; ReCalc(u);
} int main () { File(); n = read(); m = read();
For (i, 1, n) a[i] = read();
For (i, 1, n - 1) {
int u = read(), v = read();
G[u].push_back(v); G[v].push_back(u);
}
Ans = 0; Dfs_Init(1); printf ("%lld\n", Ans);
For (i, 1, m) {
int pos = read(), val = read();
a[pos] += val; Link_Cut_Tree :: Access(pos, val);
printf ("%lld\n", Ans);
} return 0;
}