Description
有一棵初始为空的树，每次新给出一个点的父亲和它连向父亲边的权值以及这个点的权值，每次加点之后询问有多少点满足 $dis(i,j)\leq val_i+val_j$，强制在线。
$n\leq10^5$。
Solution
如果树是静态的，那么这是个点分治裸题：把条件拆成 $dis(i,root)-val_i\leq -dis(root, j)+val_j$，用平衡树维护即可。
现在我们动态加儿子，可以尝试用点分树维护。当一个点分树上一个子树的大小过于不平衡直接重构这个点分树即可。
复杂度 $O(n\log^3n)$。
听起来很简单是吧，实际上写起来还是有点复杂的。
按照常规套路，在每个点维护两棵平衡树，分别代表这个点在点分树上子树内所有点在原树上到该点的信息、这个点在点分树上子树内所有点在原树上到原树上该点父亲的信息，然后查询的时候减一下去掉重复统计的部分。
重构怎么办呢？
感觉上我们需要把整个子树都重建一遍，别的还好说，但我们要重构的这棵树的根到他父亲的信息似乎不是很好维护，然后有一个 trick，直接把原来的平衡树挪到新根上就好了！
平衡树显然需要写一个垃圾回收。
Code
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
const int maxn = 1e5 + 10;
int dep[maxn];
struct edge
{
int y, w;
};
std::vector<edge> e[maxn];
namespace tree
{
int father[maxn][20], dis_rt[maxn];
inline void add(int x, int y, int w) { e[x].push_back({y, w}), e[y].push_back({x, w}); }
void add_node(int x, int fa, int w)
{
father[x][0] = fa;
if (fa)
add(x, fa, w);
dep[x] = dep[fa] + 1, dis_rt[x] = dis_rt[fa] + w;
for (int i = 1; i <= 18; i++)
father[x][i] = father[father[x][i - 1]][i - 1];
}
int lca(int x, int y)
{
if (dep[x] < dep[y])
std::swap(x, y);
int d = dep[x] - dep[y];
for (int i = 0; d; d >>= 1, i++)
if (d & 1)
x = father[x][i];
if (x == y)
return x;
for (int i = 18; i >= 0; i--)
if (father[x][i] != father[y][i])
x = father[x][i], y = father[y][i];
return father[x][0];
}
int dis(int x, int y) { return dis_rt[x] + dis_rt[y] - 2 * dis_rt[lca(x, y)]; }
}
using tree::dis;
namespace Treap
{
int top;
struct Node
{
int val, siz, rnd, num;
Node *son[2];
inline void push_up()
{
siz = num;
if (son[0])
siz += son[0]->siz;
if (son[1])
siz += son[1]->siz;
}
} a[maxn * 100], *bin[maxn * 100];
inline Node *new_node(int val)
{
Node *res = bin[--top];
res->son[0] = res->son[1] = nullptr;
res->siz = res->num = 1, res->val = val, res->rnd = rand();
return res;
}
inline void del_node(Node *p) { bin[top++] = p; }
inline void rotate(Node *&x, int d) // 0:right 1:left
{
Node *t = x->son[d];
x->son[d] = t->son[d ^ 1], t->son[d ^ 1] = x;
x->push_up(), t->push_up();
x = t;
}
void insert(Node *&x, int val)
{
if (!x)
{
x = new_node(val);
return;
}
x->siz++;
if (x->val == val)
{
x->num++;
return;
}
int d = val > x->val;
insert(x->son[d], val);
if (x->son[d]->rnd < x->rnd)
rotate(x, d);
}
void remove(Node *&x)
{
if (!x)
return;
remove(x->son[0]), remove(x->son[1]);
del_node(x), x = nullptr;
}
int rank(Node *x, int k)
{
if (!x)
return 0;
if (k < x->val)
return rank(x->son[0], k);
else
return rank(x->son[1], k) + x->num + (x->son[0] ? x->son[0]->siz : 0);
}
struct init
{
init()
{
for (int i = 0; i < maxn * 100; i++)
bin[top++] = &a[i];
}
} init_;
}
Treap::Node *fa[maxn], *self[maxn];
using Treap::insert;
using Treap::rank;
using Treap::remove;
int val[maxn];
int father[maxn];
namespace divide
{
std::set<int> son[maxn];
int time, is[maxn], tot, all, siz[maxn], root, mx[maxn];
int vis[maxn];
void remove(int x)
{
is[x] = time, tot++;
remove(self[x]);
for (auto i : son[x])
remove(i), remove(fa[i]);
son[x].clear();
}
void get_siz(int x, int fa, int dep)
{
siz[x] = 1, mx[x] = 0;
for (auto v : e[x])
if (is[v.y] == time && vis[v.y] != time && v.y != fa)
get_siz(v.y, x, dep + v.w), siz[x] += siz[v.y], mx[x] = std::max(mx[x], siz[v.y]);
mx[x] = std::max(mx[x], all - siz[x]);
if (mx[x] < mx[root])
root = x;
}
void dfs(int x, int fa, int dep, Treap::Node *&p)
{
insert(p, dep - val[x]);
for (auto v : e[x])
if (is[v.y] != time || v.y == fa || vis[v.y] == time)
continue;
else
dfs(v.y, x, dep + v.w, p);
}
void solve(int x)
{
vis[x] = time;
dfs(x, 0, 0, self[x]);
for (auto v : e[x])
{
if (is[v.y] != time || vis[v.y] == time)
continue;
root = 0, mx[root] = 1 << 30, all = siz[v.y];
get_siz(v.y, x, 0), get_siz(root, x, 0);
dfs(v.y, 0, v.w, fa[root]), father[root] = x, son[x].insert(root);
solve(root);
}
}
void rebuild(int x)
{
time++;
tot = 0;
int f = father[x];
son[f].erase(x);
Treap::Node *tmp = fa[x];
fa[x] = nullptr;
remove(x);
root = 0, mx[root] = 1 << 30, all = tot;
get_siz(x, 0, 0), get_siz(root, 0, 0);
father[root] = f, son[f].insert(root);
fa[root] = tmp;
solve(root);
}
}
int add(int x, int f, int w, int vall)
{
tree::add_node(x, f, w);
val[x] = vall;
divide::son[father[x] = f].insert(x);
int res = rank(self[x], vall);
insert(self[x], -vall);
for (int i = x; father[i]; i = father[i])
{
int f = father[i], w = dis(x, f);
res += rank(self[f], vall - w);
res -= rank(fa[i], vall - w);
insert(fa[i], w - vall), insert(self[f], w - vall);
}
int flag = 0;
for (int i = x; father[i]; i = father[i])
if (self[i]->siz > self[father[i]]->siz * 0.8)
flag = father[i];
if (flag)
divide::rebuild(flag);
return res;
}
int main()
{
int u;
scanf("%d", &u);
int n;
scanf("%d", &n);
long long ans = 0;
for (int i = 1, a, c, r; i <= n; i++)
{
scanf("%d%d%d", &a, &c, &r);
a = a ^ (ans % 1000000000);
printf("%lld\n", ans += add(i, a, c, r));
}
}