【ZJOI2018】历史

【ZJOI2018】历史

该来的总归还是会来的……

题意：

题目传送门

题解：

考虑把题意转化成一个更加科学一点的模型，发现这个崛起操作类似于\(LCT\)的\(Access\)操作，继续分析一下，发现每次崛起的灾难度就是这次\(Access\)的轻重链的切换次数。那么题目就转化成了给出一个\(Access\)的顺序，让操作完之后的轻重链切换次数最大。

接下来考虑什么时候会造成轻重链的切换。显然，对于一个点\(x\)，如果\(x\)所引出的重链发生了改变，那么说明来自\(x\)的两个不同子树中的节点进行了\(Access\)操作。

另一个容易发现的的结论就是每个点对于答案的贡献是独立的，所以我们可以单独计算每个点的贡献。我们记\(Ans_x\)表示\(x\)节点处轻重链切换次数的最大值，那么答案就是\(\sum_x Ans_x\)。

接下来考虑如何计算一个点轻重链切换次数的最大值，我们记\(A_v\)表示\(v(v \in son_x)\)这个子树中的\(Access\)次数。我们实际上可以将问题的模型进行再次转化，对于一个点\(x\)，我们把\(x\)子树中的所有\(Access\)操作看成一个小球，在\(x\)同一个孩子节点的子树下的球颜色一样，现在需要安排一个球的摆放顺序，使得相邻两个球颜色不同的数量最多。

考虑一种贪心构造的方法，我们记\(Mx_x\)表示\(x\)的孩子节点中\(A\)最大的值，如果\(Mx_x * 2 > A_x + 1\)，那么答案就是\(2 * (A_x - Mx_x)\)，否则答案就是\(A_x - 1\)。这个是容易证明的，我们尝试把其他颜色的球放在颜色最多的球的间隔中，如果放的满，那么此时其余颜色的球最少为\(Mx_x - 1\)，答案就是球的个数减一，即\(A_x - 1\)，否则说明一些颜色最多的球会放在一起，那么答案就是其余颜色球的个数乘以\(2\)，即\(2 * (A_x - Mx_x)\)。

于是我们现在就有了一个\(O(n)\)计算贡献的方法了。考虑如何优化。

对于一个点\(u\)，如果某个点\(v\)的\(A_v * 2 > A_u + 1\)，那么我们就记\(u\)到\(v\)的边为重边，否则为轻边，这样我们的答案可以简单的计算了，如果\(u\)没有重边，那么答案就是\(A_x - 1\)，否则就是\(2 * (A_x - A_{heavyson})\)。

我们发现，对于一次修改，影响到的就是\(x\)到根的一条链。对于经过的边，我们分情况讨论：

如果经过的边是重边，由于每次加上的一定是一个正整数，所以原本是重边的边仍然是重边，并且答案不变，因为\(A_x\)和\(Mx_x\)都变大了\(w_i\)。

如果经过的边是轻边，那么这次修改操作可能会让它变成重边，那么我们判断其是否会变成重边，然后重新计算一下答案即可。

为什么这样复杂度是正确的呢？考虑每经过一条轻边，\(A\)的值至少会乘以\(2\)，那么轻边的个数最多为\(log\)值域 级别的。所以每次修改只会修改\(log\)次。

至于如何维护这棵树呢？一种方法是使用\(LCT\)，稍微不同的是\(Access\)操作的时候不是将到根的所有边都设置成重边，而是按照上述的方法判断是否切换。然后复杂度分析仍然是按照\(LCT\)的分析，还是一样的。

Code：

#include 
using namespace std;
const int N = 4e5 + 50;
typedef long long ll;int n, m, tot;
ll a[N], res[N];
ll ans;
int heav[N], head[N];
struct edge {int to, nxt;
}E[N << 1];namespace LCT {struct node {int ch[2];int fa;ll sum, tag;}t[N << 1];
#define ls(o) t[o].ch[0]
#define rs(o) t[o].ch[1]
#define pa(o) t[o].faint Which(int o) { return rs(pa(o)) == o; }int Isroot(int o) { return ls(pa(o)) != o && rs(pa(o)) != o; }void Apply(int o, ll v) { t[o].sum += v; t[o].tag += v; }void Down(int o) {if(!o || !t[o].tag) return ;if(ls(o)) Apply(ls(o), t[o].tag);if(rs(o)) Apply(rs(o), t[o].tag);t[o].tag = 0;}void Rotate(int o) {int f = pa(o), ff = pa(f), c = Which(o);if(!Isroot(f)) t[ff].ch[Which(f)] = o; t[o].fa = ff;pa(t[o].ch[c ^ 1]) = f; t[f].ch[c] = t[o].ch[c ^ 1];t[o].ch[c ^ 1] = f; t[f].fa = o;}void TreeDown(int o) { if(!Isroot(o)) TreeDown(pa(o)); Down(o); }void Splay(int o) {TreeDown(o);for(; !Isroot(o); Rotate(o)) {if(!Isroot(pa(o))) Rotate( Which(o) ^ Which(pa(o)) ? o : pa(o));}}int Findroot(int o) {while(ls(o)) Down(o), o = ls(o);return o;}void Getans(int o) {ans -= res[o];res[o] = heav[o] ? (2ll * (t[o].sum - t[heav[o]].sum)) : (t[o].sum - 1);if(a[o] * 2 > t[o].sum + 1) res[o] = 2ll * (t[o].sum - a[o]);ans += res[o];}void Access(int o, ll v) {a[o] += v;for(int y = 0; o; y = o, o = pa(o)) {Splay(o);t[o].sum += v;if(ls(o)) Apply(ls(o), v);if(heav[o]) {TreeDown(heav[o]);if(t[heav[o]].sum * 2 <= t[o].sum + 1) heav[o] = 0, rs(o) = 0;}int v = Findroot(y);if(t[v].sum * 2 > t[o].sum + 1) heav[o] = v, rs(o) = v;Getans(o);}}
}
using namespace LCT;void Addedge(int u, int v) {E[++tot].to = v; E[tot].nxt = head[u]; head[u] = tot;
}void Dfs(int o, int fa) {t[o].fa = fa; t[o].sum = a[o];ll Mx = -1, pos;for(int i = head[o]; ~i; i = E[i].nxt) {int to = E[i].to;if(to == fa) continue;Dfs(to, o);t[o].sum += t[to].sum;if(t[to].sum > Mx) { Mx = t[to].sum; pos = to; }}if(Mx * 2 > t[o].sum + 1) heav[o] = pos;Getans(o);rs(o) = heav[o];
}int main() {memset(head, -1, sizeof head);scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);for(int i = 1, u, v; i < n; i++) {scanf("%d%d", &u, &v);Addedge(u, v); Addedge(v, u);}Dfs(1, 0);printf("%lld\n", ans);for(int i = 1; i <= m; i++) {int x; ll y;scanf("%d%lld", &x, &y);Access(x, y);printf("%lld\n", ans);}return 0;
}

转载于:https://www.cnblogs.com/Apocrypha/p/10732346.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！