gmoj 6874. 【2020.11.19提高组模拟】ZYT的解决方案: 通过(Code(rotate root dp))实现
最编程
2023-12-31 10:18:45
...
#include <cstdio>
#include <vector>
#define N 100010
#define ll long long
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mem(x, a) memset(x, a, sizeof x)
#define mpy(x, y) memcpy(x, y, sizeof y)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
#define go(x) for (int p = tail[x], v; p; p = e[p].fr)
using namespace std;
struct pr{int v, cost;};
struct node{int v, fr;}e[N << 1];
int n, m, tail[N], cnt = 0, val[N], ans = 0, dep[N];
int dfn[N], fa[N][18], siz[N], tot = 0, t[N << 2], lazy[N << 2];
vector<pr> up[N], dn[N];
inline int read() {
int x = 0, f = 0; char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
inline void add(int u, int v) {e[++cnt] = (node){v, tail[u]}; tail[u] = cnt;}
void dfs(int x) {
dfn[x] = ++tot, siz[x] = 1;
for (int i = 0; fa[fa[x][i]][i]; i++)
fa[x][i + 1] = fa[fa[x][i]][i];
go(x) if ((v = e[p].v) != fa[x][0]) {
dep[v] = dep[x] + 1, fa[v][0] = x;
dfs(v), siz[x] += siz[v];
}
}
void update(int x, int l, int r) {
if (l == r) {lazy[x] = 0; return;}
t[ls] += lazy[x], lazy[ls] += lazy[x];
t[rs] += lazy[x], lazy[rs] += lazy[x];
lazy[x] = 0;
}
void modify(int x, int l, int r, int fl, int fr, int value) {
if (lazy[x]) update(x, l, r);
if (fl <= l && r <= fr) {
t[x] += value, lazy[x] += value;
update(x, l, r); return;
}
int mid = (l + r) >> 1;
if (fl <= mid) modify(ls, l, mid, fl, fr, value);
if (fr > mid) modify(rs, mid + 1, r, fl, fr, value);
t[x] = max(t[ls], t[rs]);
}
void down_modify(int x, int zf) {
int len = dn[x].size() - 1;
fo(i, 0, len) {
int vv = dn[x][i].v;
modify(1, 1, n, dfn[vv], dfn[vv] + siz[vv] - 1, zf * dn[x][i].cost);
}
}
int pa_son(int v, int u) {
int now_ = v;
for (int i = 0, cha = dep[v] - dep[u] - 1; cha > 0; cha >>= 1, i++)
if (cha & 1) now_ = fa[now_][i];
return now_;
}
void up_modify(int x, int zf) {
int len = up[x].size() - 1;
fo(i, 0, len) {
int vv = up[x][i].v;
if (dfn[vv] <= dfn[x] && dfn[x] <= dfn[vv] + siz[vv] - 1) {
modify(1, 1, n, 1, n, zf * up[x][i].cost);
int now_ = pa_son(x, vv);
modify(1, 1, n, dfn[now_], dfn[now_] + siz[now_] - 1, zf * -up[x][i].cost);
}
else modify(1, 1, n, dfn[vv], dfn[vv] + siz[vv] - 1, zf * up[x][i].cost);
}
}
void self_modify(int x, int v, int cz) {
if (1 <= dfn[x] - 1) modify(1, 1, n, 1, dfn[x] - 1, cz * val[x]);
if (dfn[x] + siz[x] <= n) modify(1, 1, n, dfn[x] + siz[x], n, cz * val[x]);
modify(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, cz * -val[x]);
}
int find(int x, int l, int r, int f) {
if (lazy[x]) update(x, l, r);
if (l == r) return t[x];
int mid = (l + r) >> 1, s = 0;
if (f <= mid) s = find(ls, l, mid, f);
else s = find(rs, mid + 1, r, f);
t[x] = max(t[ls], t[rs]);
return s;
}
void for_answer(int x, int zf) {
if (1 <= dfn[x] - 1) modify(1, 1, n, 1, dfn[x] - 1, zf * val[x]);
if (dfn[x] + siz[x] <= n) modify(1, 1, n, dfn[x] + siz[x], n, zf * val[x]);
}
void rotate(int x) {
up_modify(x, 1);
for_answer(x, 1);
ans = max(ans, t[1]);
for_answer(x, -1);
go(x) {
if ((v = e[p].v) == fa[x][0]) continue;
self_modify(x, v, 1);
down_modify(v, -1);
rotate(v);
down_modify(v, 1);
self_modify(x, v, -1);
}
up_modify(x, -1);
}
int main()
{
freopen("score.in", "r", stdin);
freopen("score.out", "w", stdout);
n = read(), m = read();
fo(i, 2, n) {
int u = read(), v = read();
add(u, v), add(v, u);
}
dfs(1);
fo(i, 1, m) {
int u = read(), v = read(), w = read();
if (u == v) {
modify(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, w);
val[u] += w; continue;
}
if (dfn[u] <= dfn[v] && dfn[v] <= dfn[u] + siz[u] - 1) {
modify(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, w);
int now_ = v;
for (int i = 0, cha = dep[v] - dep[u] - 1; cha > 0; cha >>= 1, i++)
if (cha & 1) now_ = fa[now_][i];
dn[now_].push_back((pr){v, w});
}
else up[u].push_back((pr){v, w});
}
rotate(1);
printf("%d\n", ans);
return 0;
}
原文地址:https://www.cnblogs.com/jz929/p/14008104.html