题解：P11803 【MX-X9-T7】『GROI-R3』此花绽放之时

xxxxxzy · 2025-04-09 12:50:54 · 题解

写篇学习笔记。

套路的考虑给每个极大连通块选最上面点的作为代表元，每次给同色连通块修改，将 u 的标记表示为 (c,v)， 代表如果 col_u = c，就 a_u \to a_u + v。

考虑到，修改链上的颜色会对标记的下传造成影响，比如修改点 w 下方的与 w 同连通块的 (u,v)，会导致 w 的标记无法下传到 (u,v) 以下的地方。

又观察到，颜色修改只会对链进行修改，所以可以考虑把链上方的标记全部下放至链下方，也就是对链的两个端点 (u,v) 进行 (rt,u) 和 (rt,v) 的标记下放，记这个操作为 \text{pway}(u),\text{pway}(v)。

考虑标记如何进行合并，第一维 c 对每种颜色开一颗动态开点线段树，这样标记就可以合并了。观察到，每次对 u 标记下放，只需要下放当前 col_u 的标记，因为其他的标记并没有意义，这样下放的 tag 也是一个 (c,v) 的形式。

套路地，树剖并维护非轻儿子。

考虑对重链中的一个点 u 加上标记 (c,v) 如何快速更新，首先找到 u 以下的且和 u 形成连通块的极长 \text{dfn} 序区间全部加上标记 (c,v)，为了统计答案，再开一个树状数组来区间修改。

快速维护单点颜色和 \text{dfn} 序上极大连通块可以采用 ODT 快速实现，不过值得注意的是，每次应将两个相邻的同颜色区间合并。

再考虑如何更新轻儿子，会发现原来的标记会对轻儿子多次下放，或者会下放不了，为了解决这个问题，拿一个 map 记录 s_{u,col} 代表 u 从父亲节点接受了多少 c=col 的标记。

这样链修改颜色的操作就维护完了，继续考虑剩下两个操作，首先是连通块加，通过不断往上跳重链找到连通块的代表元并打上标记；其次是查询，只需要对查询节点 u 进行 \text{pway(u)} 然后输出 u 的值即可。

代码部分参考了 @lsj2009 的代码。

#include <bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<ll, ll>
#define mp make_pair
#define pb emplace_back
#define ld lower_bound
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define drep(i, a, b) for (int i = (a); i >= (b); i--)
#define U(i, a, b) for (int i = (a); i < (b); i++)
#define F for
#define W while
#define ud upper_bound
#define mem(s, k) memset(s, k, sizeof(s))
#define fi first
#define se second
#define ull unsigned long long
#define vec vector <int>
#define fv inline void
#define fn inline static
using u16 = unsigned short; using u32 = unsigned; using u64 = unsigned ll; using u128 = __uint128_t;
using i16 = short; using i32 = int; using i64 = ll; using i128 = __int128_t;
using namespace std;
const i32 N = 2e5 + 5;
i32 n;
struct SGT {
  struct node { i32 ls, rs; i64 t; }seg[N * 80];
  i32 tot;
  i32 newnode() { return ++tot; }
  fv upd(i32 &p, i32 ql, i32 qr, i64 v, i32 l = 1, i32 r = n) {
    if (ql > r || qr < l) return ;
    if (!p) p = newnode();
    if (ql <= l && r <= qr) return (void)(seg[p].t += v);
    i32 mid = (l + r) >> 1;
    upd(seg[p].ls, ql, qr, v, l, mid);
    upd(seg[p].rs, ql, qr, v, mid + 1, r);
  }
  inline i64 qry(i32 p, i32 x, i32 l = 1, i32 r = n) {
    if (!p || x > r || x < l) return 0;
    if (l == r) return seg[p].t;
    i32 mid = (l + r) >> 1;
    return qry(seg[p].ls, x, l, mid) + qry(seg[p].rs, x, mid + 1, r) + seg[p].t;
  }
}T;
struct node { i32 l, r; mutable i32 v; };
bool operator < (const node &x, const node &y) { return x.l < y.l; }
struct ODT {
  set <node> S;
  inline auto split(i32 pos) {
    auto it = S.ld({pos, -1, 0});
    if (it != S.end() && it->l == pos) return it;
    --it; i32 l = it->l, r = it->r, v = it->v;
    S.erase(it); S.insert({l, pos - 1, v});
    return S.insert({pos, r, v}).fi;
  }
  fv emerge(i32 l, i32 r, i32 x) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; it++);
    S.erase(itl, itr);
    auto p = S.insert({l, r, x}).fi; itl = itr = p;
    bool L = 0, R = 0;
    while (itl -> v == p -> v) itl--;
    while (itr -> v == p -> v) itr++; --itr;
    if (!L) itl++;
    l = itl -> l, r = itr -> r, x = p -> v;
    S.erase(itl, ++itr), S.insert({l, r, x});
  }
  inline pii qryLR(i32 x) { auto it = --S.ud({x, -1, 0}); return mp(it->l, it->r); }
  inline i32 qry(i32 x) { auto it = --S.ud({x, -1, 0}); return it->v; }
} S[N];
struct BIT {
  i64 c[N];
  fv upd(i32 x, i64 v) { for (; x < N; x += x & -x) c[x] += v; }
  inline i64 qry(i32 x) { i64 ans = 0; for (; x; x -= x & -x) ans += c[x]; return ans; }
  fv upd(i32 l, i32 r, i64 v) { upd(l, v), upd(r + 1, -v); }
}B;
map <i32, i64> c[N];
i32 son[N], dfn[N], tp[N], siz[N], rt[N], dep[N], fa[N], id[N], ed[N], tot;
vec G[N];
fv dfs1(i32 u, i32 f) {
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  for (i32 v : G[u]) {
    if (v == f) continue;
    dfs1(v, u), siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}
fv dfs2(i32 u, i32 top) {
  tp[u] = top, dfn[u] = ++tot, id[tot] = u;
  ed[top] = max(ed[top], tot);
  if (son[u]) dfs2(son[u], top);
  for (i32 v : G[u]) {
    if (v == fa[u] || v == son[u]) continue;
    dfs2(v, v);
  }
}
fv upd(i32 u, i64 k, i32 op = 1) {
  i32 col = S[tp[u]].qry(dfn[u]);
  auto [l, r] = S[tp[u]].qryLR(dfn[u]);
  l = max((i32)l, (i32)dfn[u]);
  if (op != 2) c[col][u] += k;
  if (op) T.upd(rt[col], l, r, k), B.upd(l, r, k);
}
fv pd(i32 u, i32 op = 1) { //fa -> u
  if (u == 1) return ;
  i32 col = S[tp[u]].qry(dfn[u]);
  i64 tag = T.qry(rt[col], dfn[fa[u]]) - c[col][u];
  upd(u, tag, op);
}
i32 stk[N], stp;
fv pway(i32 u) {
  stp = 0;
  while (tp[u] != 1) stk[++stp] = tp[u], u = fa[tp[u]];
  drep (i, stp, 1) pd(stk[i]);
}
fv upd1(i32 u, i32 v, i32 c) {
  pway(u), pway(v);
  while (tp[u] != tp[v]) {
    if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
    S[tp[u]].emerge(dfn[tp[u]], dfn[u], c);
    pd(tp[u], 0), u = fa[tp[u]];
  }
  if (dep[u] > dep[v]) swap(u, v);
  S[tp[u]].emerge(dfn[u], dfn[v], c);
  if (u == tp[u]) pd(u, 0);
}
fv upd2(i32 u, i64 k) {
  i32 up = 1, c = S[tp[u]].qry(dfn[u]);
  while (u) {
    auto [l, r] = S[tp[u]].qryLR(dfn[u]);
    if (S[tp[u]].qry(dfn[u]) != c) break;
    if (l != dfn[tp[u]]) { up = id[l]; break; }
    up = tp[u], u = fa[tp[u]];
  }
  upd(up, k, 2);
}
fn i64 qsum(i32 u) { pway(u); return B.qry(dfn[u]); }
i32 op, u, v, k, q, col[N];
int main() {
  IOS;
  cin >> n >> q;
  rep (i, 1, n) cin >> col[i];
  rep (i, 2, n) cin >> u, G[u].pb(i);
  dfs1(1, 0), dfs2(1, 1);
  rep (i, 1, n) if (tp[i] == i) S[i].S.insert({0, n + 1, 0});
  rep (i, 1, n) S[tp[i]].emerge(dfn[i], dfn[i], col[i]);
  rep (i, 1, q) {
    cin >> op >> u;
    if (op == 1) cin >> v >> k, upd1(u, v, k);
    else if (op == 2) cin >> k, upd2(u, k);
    else cout << qsum(u) << "\n";
  }
}