首页分享 Solution

Solution

来源：花匠小妙招时间：2024-12-11 18:22

Description" role="presentation">Description

Link.

维护一棵树，初始时树空。接下来 n" role="presentation">n 次操作，每次操作加入一片叶子 u" role="presentation">u，u" role="presentation">u 到其邻接点的边权为 w" role="presentation">w，u" role="presentation">u 的半径为 ru" role="presentation">ru。每次加入结点后，求出 ∑u<v[ru+rv≥dist⁡(u,v)]" role="presentation">∑u<v[ru+rv≥dist⁡(u,v)] 的值。强制在线。

n≤105" role="presentation">n≤105。

Solution" role="presentation">Solution

初学 OI 的时候，第一次听说所谓“超级难写的毒瘤题”就是《紫荆花之恋》，后来每次向尝试也不知道为什么都咕掉了。这几天抽空写了一发却发现……这种码量顶多叫难写，写出来也没啥新奇了。还是挺感慨。（

显然答案可以随着树的变化维护增量。考虑在一棵静态的树上，对于固定的 x" role="presentation">x，如何快速求出 ∑u≠x[ru+rx≥dist⁡(u,x)]" role="presentation">∑u≠x[ru+rx≥dist⁡(u,x)]——要说“维护”这一值，那么可以点分树套平衡树维护。注意本题得用小常数的平衡树（例如替罪羊树）。

怎么动态维护点分树树形？也可以像替罪羊一样，发现子树不平衡就点分治重构。总复杂度套用替罪羊的证明可知为 O(nlog2⁡n)" role="presentation">O(nlog2⁡n)。

Code" role="presentation">Code

巨大常数，代码就自己写嘛 qwq。

/*+Rainybunny+*/ #include <bits/stdc++.h> #define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i) #define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i) typedef long long LL; inline char fgc() { static char buf[1 << 17], *p = buf, *q = buf; return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q) ? EOF : *p++; } template <typename Tp = int> inline Tp rint() { Tp x = 0, s = fgc(), f = 1; for (; s < '0' || '9' < s; s = fgc()) f = s == '-' ? -f : f; for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0'); return x * f; } template <typename Tp> inline void wint(Tp x) { if (x < 0) putchar('-'), x = -x; if (9 < x) wint(x / 10); putchar(x % 10 ^ '0'); } template <typename Tp> inline void chkmin(Tp& u, const Tp& v) { v < u && (u = v, 0); } template <typename Tp> inline void chkmax(Tp& u, const Tp& v) { u < v && (u = v, 0); } template <typename Tp> inline Tp imin(const Tp& u, const Tp& v) { return u < v ? u : v; } template <typename Tp> inline Tp imax(const Tp& u, const Tp& v) { return u < v ? v : u; } const int MAXN = 1e5; const double LUCK = 0.712; // const double LUCK = 1.; int n; class ScapegoatTree { private: static const int MAXND = 8e6; int node, ch[MAXND][2], siz[MAXND]; LL val[MAXND]; int cnt[MAXND], sum[MAXND], rcyc[MAXND]; inline int newnd() { int u = rcyc[0] ? rcyc[rcyc[0]--] : ++node; ch[u][0] = ch[u][1] = val[u] = 0, cnt[u] = sum[u] = siz[u] = 1; return u; } inline void pushup(const int u) { siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1; sum[u] = sum[ch[u][0]] + sum[ch[u][1]] + cnt[u]; } inline bool valid(const int u) { return imax(siz[ch[u][0]], siz[ch[u][1]]) <= siz[u] * LUCK + 5; } inline void collect(const int u, int*& idx) { if (!u) return ; collect(ch[u][0], idx), *idx++ = u, collect(ch[u][1], idx); } inline int rebuild(const int* buc, const int l, const int r) { if (l > r) return 0; int mid = l + r >> 1, u = buc[mid]; ch[u][0] = rebuild(buc, l, mid - 1); ch[u][1] = rebuild(buc, mid + 1, r); return pushup(u), u; } inline void balance(int& u) { if (valid(u)) return ; static int buc[MAXN + 5], *idx; collect(u, idx = buc), u = rebuild(buc, 0, idx - buc - 1); } public: inline void recycle(const int u) { if (!u) return ; rcyc[++rcyc[0]] = u; recycle(ch[u][0]), recycle(ch[u][1]); } inline void insert(int& u, const LL x) { if (!u) return u = newnd(), val[u] = x, void(); balance(u); if (val[u] == x) return ++cnt[u], ++sum[u], void(); else if (val[u] < x) insert(ch[u][1], x); else insert(ch[u][0], x); pushup(u); } inline int rank(const int rt, const LL x) { // count elements <= x. int u = rt, ret = 0; while (u) { if (val[u] == x) return ret + sum[ch[u][0]] + cnt[u]; else if (val[u] < x) ret += sum[ch[u][0]] + cnt[u], u = ch[u][1]; else u = ch[u][0]; } return ret; } } sct; namespace LCA { const int MAXLG = 16; int dep[MAXN + 5], fa[MAXN + 5][MAXLG + 2]; LL dis[MAXN + 5]; inline void append(const int u, const int f, const int w) { fa[u][0] = f, dep[u] = dep[f] + 1, dis[u] = dis[f] + w; for (int i = 1; fa[u][i - 1]; fa[u][i] = fa[fa[u][i - 1]][i - 1], ++i); } inline int lca(int u, int v) { if (dep[u] < dep[v]) u ^= v ^= u ^= v; per (i, MAXLG, 0) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i]; if (u == v) return u; per (i, MAXLG, 0) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0]; } inline LL dist(const int u, const int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; } } // namespace LCA. namespace DivideTree { int vfa[MAXN + 5], rad[MAXN + 5], ecnt, head[MAXN + 5]; struct Edge { int to, nxt; } graph[MAXN * 2 + 5]; inline void link(const int u, const int v) { graph[++ecnt] = { v, head[u] }, head[u] = ecnt; graph[++ecnt] = { u, head[v] }, head[v] = ecnt; } std::vector<int> inc[MAXN + 5]; bool foc[MAXN + 5]; int siz[MAXN + 5], wgt[MAXN + 5], srt[MAXN + 5][2]; inline void collect(const int u, const int fa, std::vector<int>& rec) { rec.push_back(u); for (int i = head[u], v; i; i = graph[i].nxt) { if (foc[v = graph[i].to] && v != fa) { collect(v, u, rec); } } } inline void findG(const int u, const int fa, const int all, int& rt) { siz[u] = 1, wgt[u] = 0; for (int i = head[u], v; i; i = graph[i].nxt) { if (foc[v = graph[i].to] && v != fa) { findG(v, u, all, rt), siz[u] += siz[v]; chkmax(wgt[u], siz[v]); } } chkmax(wgt[u], all - siz[u]); if (!rt || wgt[rt] > wgt[u]) rt = u; } inline void divide(const int u) { foc[u] = false; sct.recycle(srt[u][0]), srt[u][0] = 0; sct.recycle(srt[u][1]), srt[u][1] = 0; for (int i = head[u], v; i; i = graph[i].nxt) if (foc[v = graph[i].to]) { int rt = 0; std::vector<int> tmp; collect(v, 0, tmp); findG(v, 0, tmp.size(), rt), inc[rt].swap(tmp); vfa[rt] = u, divide(rt); } } void rebuild(const int); // pre-declare for function `update`. inline void update(int u, const int til, const bool op) { int pia = 0; LL tmpd = 0; for (int las = 0, v = u; v != til; v = vfa[las = v]) { if (op) inc[v].push_back(u); sct.insert(srt[v][0], tmpd - rad[u]); if (vfa[v]) { sct.insert(srt[v][1], (tmpd = LCA::dist(u, vfa[v])) - rad[u]); } if (las && inc[las].size() > inc[v].size() * LUCK + 5) pia = v; } if (pia) rebuild(pia); } inline void rebuild(const int u) { int vf = vfa[u], rt = 0; for (int v: inc[u]) foc[v] = true; findG(u, 0, inc[u].size(), rt), inc[rt].swap(inc[u]); vfa[rt] = vf, divide(rt); for (int v: inc[rt]) update(v, vfa[rt], 0); } inline void append(int u, const int rfa, const int r) { link(u, rfa); vfa[u] = rfa, rad[u] = r, update(u, 0, 1); } inline int contri(const int u) { int ret = sct.rank(srt[u][0], rad[u]) - 1; for (int las = u, v = vfa[u]; v; v = vfa[las = v]) { LL d = LCA::dist(u, v); ret += sct.rank(srt[v][0], rad[u] - d) - sct.rank(srt[las][1], rad[u] - d); } return ret; } } // namespace DivideTree. int main() { rint(), n = rint(); LL ans = 0; rep (i, 1, n) { int a = rint() ^ (ans % 1'000'000'000), c = rint(), r = rint(); LCA::append(i, a, c); DivideTree::append(i, a, r); ans += DivideTree::contri(i); wint(ans), putchar('n'); } return 0; }