Description
若带点权、边权的树上一对 \((u, v)\) 为 friend，那么需要满足 \(\text{dist}(u, v) \le r_u + r_v\)，其中 \(r_x\) 为点 \(x\) 的权，\(\text{dist}(u, v)\) 表示 \(u, v\) 的树上距离，即 \(u, v\) 间的简单路径上的边权和。
一开始树为空，之后有 \(n\) 次加点操作，每次各处该点需要连接的结点、点权以及边权。对于每次加点之后得到的树，你需要输出当前树上 friends 的对数。强制在线。
Hint
\(1\le n\le 10^5, 1\le \text{边权}\le 10^4, 1\le \text{点权}\le 10^9\)。
Solution
这里的加点操作非常难搞，因此不妨试着先离线。如果可以离线，我们可以先把树建出来，一开始 \(\forall i\in[1, n],r_i\leftarrow -\infty\)，然后一个个将点权修改。这就不难用 动态点分治 维护。
考虑将原来的式子进行变形：\(\text{dist}(u, v) \le r_u + r_v \quad\longrightarrow\quad r_v - \text{dist}(u, v) \le -r_u\)，然后就是对于每个 \(u\) 数一数满足条件的 \(v\) 的个数。
这比较显然可以用 平衡树 维护，不过在跑点分树的过程中，如果直接将答案加上点分子树的贡献，会与其祖先的答案算重。于是再对点分树父亲维护一颗平衡树用作 容斥。这样一次修改是 \(O(\log^2 n)\) 的，而答案显然可以在修改时计算影响。
于是现在我们有 \(O(n\log^2 n)\) 的离线算法了。
考虑在线化改造这个算法。如果不做改动，每次插入建一次点分树的话复杂度会变成 \(O(n^2\log^2 n)\)；而如果插入节点后干脆不对点分树做改动的话，众所周知仍然会被卡，不该也不行。
于是尝试均摊一下这两部分。如果我们选择根号重构，那么树高只能控制在 \(O(\sqrt{n})\)，这样复杂度为 \(O(n^{1.5}\log n)\)，并不理想。
但如果选择替罪羊式重构的话，我们的树高就能被控制在 \(O(\log n)\)。所谓替罪羊式重构，就是对于一个结点如果它的某一子树的大小占据的整颗子树的 \(\alpha(\approx 0.8)\) 倍，那么就部分重构这颗子树。
这样的复杂度是均摊 \(O(n\log^2 n)\) 的，并且做到了在线。
写起来真的非常复杂，而且需要注意常数。优化技巧：
- 使用较快的平衡树，不要用 Splay 或 FHQ-Treap；
- 计算树上距离不需要再写一个 LCA，直接记录每个点到祖先的距离即可。因为一个点的祖先数不超过 \(O(\log n)\)；
- 重构选择深度最浅的重构点进行重构；
- Fast IO method。
Code
附上 Luogu 上卡到 Page 1（2020.10.14）的代码：
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : WC2014 紫荆花之恋
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9;
const int LogN = 18;
struct IO {
static const int S=1<<24;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n');return *this;}
template<typename T> IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
IO&operator << (const char c){pc(c);return *this;}
template<typename T> IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);
return *this;
}
} fin, fout;
#define alpha 0.7
namespace bst_nodes { // 奇怪的平衡树实现：不平衡就旋转，这样跑的很快
struct Node {
int ch[2], val, cnt, siz;
inline Node() { }
inline Node(int l, int r, int v, int c, int s) :
val(v), cnt(c), siz(s) { ch[0] = l, ch[1] = r; }
} t[N << 6];
int total = 0;
int rec[N << 6], top = 0;
inline void create(int& x, int v) {
x = top ? rec[top--] : ++total;
t[x] = Node(0, 0, v, 1, 1);
}
inline void pushup(int& x) {
t[x].siz = t[x].cnt + t[t[x].ch[0]].siz + t[t[x].ch[1]].siz;
}
inline void rotate(int& x, int d) {
int y = t[x].ch[d];
if (t[x].siz * alpha > t[y].siz) return;
t[x].ch[d] = t[y].ch[!d];
t[y].ch[!d] = x, pushup(x), pushup(x = y);
}
void insert(int& x, int v) {
if (!x) return create(x, v), void();
++t[x].siz;
if (v == t[x].val) return ++t[x].cnt, void();
int d = v > t[x].val;
insert(t[x].ch[d], v), rotate(x, d);
}
int count(int x, int v) {
if (!x) return 0;
if (t[x].val <= v) return t[t[x].ch[0]].siz + t[x].cnt + count(t[x].ch[1], v);
else return count(t[x].ch[0], v);
}
void recycle(int& x) {
if (!x) return;
recycle(t[x].ch[0]), recycle(t[x].ch[1]);
rec[++top] = x, x = 0;
}
}
struct bst {
int root;
bst() : root(0) { }
inline void insert(int v) { bst_nodes::insert(root, v); }
inline void clear() { bst_nodes::recycle(root); }
inline int count(int v) { return bst_nodes::count(root, v); }
};
int n, Q, R[N];
long long ans = 0ll;
struct Edge {
int to, len;
Edge(int t, int l) : to(t), len(l) { }
}; vector<Edge> adj[N];
struct {
int fa[N], cnt[N], dep[N];
long long anc[N][LogN << 2];
bst t[N][2];
bool vis[N];
int siz[N], maxp[N], ctr;
inline long long dist(int x, int a) {
return anc[x][dep[a]];
}
int getSize(int x, int f) {
siz[x] = 1;
for (auto y : adj[x]) if (y.to != f && !vis[y.to])
siz[x] += getSize(y.to, x);
return siz[x];
}
void getCentr(int x, int f, int t) {
maxp[x] = 0;
for (auto y : adj[x]) if (y.to != f && !vis[y.to])
getCentr(y.to, x, t), maxp[x] = max(maxp[x], siz[y.to]);
maxp[x] = max(maxp[x], t - siz[x]);
if (maxp[ctr] > maxp[x]) ctr = x;
}
void getBst(int s, int x, int f, long long d) {
t[s][0].insert(d - R[x]);
if (fa[s]) t[s][1].insert(dist(x, fa[s]) - R[x]);
for (auto y : adj[x]) if (y.to != f && !vis[y.to])
getBst(s, y.to, x, d + y.len);
}
void getDist(int s, int x, int f, long long d) {
anc[x][dep[s]] = d;
for (auto y : adj[x]) if (y.to != f && !vis[y.to])
getDist(s, y.to, x, d + y.len);
}
int rebuild(int x, int f, int d) {
maxp[ctr = 0] = N;
getCentr(x, 0, getSize(x, 0));
int s = ctr;
vis[s] = 1, fa[s] = f, dep[s] = d, cnt[s] = 1;
t[s][0].clear(), t[s][1].clear(); getBst(s, s, 0, 0);
getDist(s, s, 0, 0);
for (auto y : adj[s]) if (!vis[y.to])
cnt[s] += cnt[rebuild(y.to, s, d + 1)];
return vis[s] = 0, s;
}
inline long long update(int i, int f, int w) {
fa[i] = f, dep[i] = dep[f] + 1;
t[i][0].insert(-R[i]);
for (int j = 1; j <= dep[f]; j++)
anc[i][j] = anc[f][j] + w;
if (i == 1) return 0ll;
adj[f].emplace_back(i, w);
adj[i].emplace_back(f, w);
int target = 0;
for (int x = i, y = fa[x]; y; y = fa[x = y]) {
long long dis = R[i] - dist(i, y);
ans += t[y][0].count(dis) - t[x][1].count(dis);
t[y][0].insert(-dis), t[x][1].insert(-dis);
if (++cnt[y] * alpha < cnt[x]) target = y;
}
if (target) {
for (int x = fa[target]; x; x = fa[x]) vis[x] = 1;
rebuild(target, fa[target], dep[target]);
for (int x = fa[target]; x; x = fa[x]) vis[x] = 0;
}
return ans;
}
} vdct;
#undef alpha
signed main() {
fin >> n, fin >> n;
for (int i = 1, f, w; i <= n; i++) {
fin >> f >> w >> R[i], f ^= ans % mod;
fout << vdct.update(i, f, w) << '\n';
}
}