BZOJ-3435. [Wc2014]紫荆花之恋

强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 $i$ 都有一个感受能力值 $r_i$，小精灵 $i,j$ 成为朋友当且仅当在树上 $i$ 和 $j$ 的距离 $\text{dist}(i,j) \leq r_i+r_j$，其中 $\text{dist}(i,j)$ 表示在这个树上从 $i$ 到 $j$ 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。

我们假定这个树一开始为空，节点按照加入的顺序从 $1$ 开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。

【输入格式】

第一行包含一个整数，表示测试点编号。

第二行包含一个正整数 $n$，表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 $\text{last_ans}$，在一开始时它的值为 $0$。

接下来 $n$ 行中第 $i$ 行有三个非负整数 $ai,ci,ri$，表示结点 $i$ 的父节点的编号为 $a_i \oplus (\text{last_ans} \bmod 10^9)$（其中 $\oplus$ 表示异或，$\text{mod}$ 表示取余，数据保证这样操作后得到的结果介于 $1$ 到 $i-1$ 之间），与父结点之间的边权为 $c_i$，节点 $i$ 上小精灵的感受能力值为 $r_i$。

注意 $a_1=c_1=0$，表示 $1$ 号节点是根结点，对于 $i>1$，父节点的编号至少为 $1$。

【输出格式】

包含 $n$ 行，每行输出 $1$ 个整数，表示加入第 $i$ 个点之后，树上有几对朋友。

【数据范围】

$n \leq 10^5$，$1 \leq c_i \leq 10^4$，$a_i \leq 2\times 10^9$，$r_i \leq 10^9$，时限 12s

这又是一道陈老师的可怕题目

首先我们来想想暴力要怎么写，和树分治类似的，考虑以 $u$ 为根的子树中，所有经过 $u$ 的路径，这样条件可以转化为

\[\text{dist}(a)+\text{dist}(b)\leq r_a+r_b\]

这里的 $\text{dist}(a)$ 表示 $a$ 到 $u$ 的距离，我们把变量归到一边

\[\text{dist}(a)-r_a\leq r_b-\text{dist}(b)\]

这样如果我们把 $u$ 子树内所有节点的 $\text{dist}(a) - r_a$ 记录下来，对于每个点 $b$，就是要查询比 $r_b - \text{dist}(b)$ 小的数有多少个，然后再扣掉来自相同子树的 $(a, b)$

这样的话再考虑加入一个点 $u$，那么 $u$ 到根路径上的所有点的子树所拥有的信息都会加上 $\text{dist}(u) - r_u$，并且要求查询的东西还是没有变，问题变成要支持加入一些数和查询小于某个值的数有多少个，所以我们用平衡树维护这个东西，然后不断往上走询问并且更新答案

但是有一个问题就是，如果碰到一条链的情况，每次都要从底走到顶，时间和空间都会变成平方级别以上。这时候可以借助替罪羊树的思想，当遇到某个节点过于不平衡，就暴力重构成平衡的东西，在这题中，最平衡的结构就是树分治的结构，因此，在重构的时候就用树分治来重构就可以了

关于实现的方法，由于要查询子树的信息，我们可以在替罪羊树的节点上用 Treap 记录下当前子树内的所有数。又因为要扣掉不合法的信息，再在这个节点记录下以它父亲（这里指的是分治结构中的父亲）为根，当前子树内的信息，这样走到它父亲的时候就可以用这个信息把不合法的减掉了

因为每次都是自底向上插入和查询，我们可以不必记录替罪羊树的儿子，只需记下父亲是谁。在重构的时候由于要遍历整棵子树、插入的时候需要知道两点间的路径长度，就需要单独保存这棵树的形态，而不是替罪羊树保存的奇怪的分治结构

另外，每个分治结构的重心和它父亲的重心不一定有直接连边，还要记录下这个分治结构中它父亲连向它的哪个节点，这样才可以在插入的时候维护刚刚所说的第二个信息，具体可以看看我的代码

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <stack>

const int MaxL = 17, MaxN = 100010, MaxS = MaxN * 60;
const int inf = ~0u >> 1;
double alpha = 0.9;

struct graph_t
{
	int total;
	int head[MaxN], point[MaxN << 1];
	int next[MaxN << 1], weight[MaxN << 1];
	int fa[MaxL][MaxN], dist[MaxN], depth[MaxN];

	void add_edge(int u, int v, int w)
	{
		weight[++total] = w;
		point[total] = v;
		next[total] = head[u];
		head[u] = total;
	}

	void add_child(int u, int f, int w)
	{
		add_edge(u, f, w);
		add_edge(f, u, w);
		fa[0][u] = f;
		dist[u] = dist[f] + w;
		depth[u] = depth[f] + 1;

		for(int i = 1; i != MaxL; ++i)
			fa[i][u] = fa[i - 1][fa[i - 1][u]];
	}

	int get_lca(int u, int v)
	{
		if(depth[u] < depth[v]) 
			std::swap(u, v);
		int diff = depth[u] - depth[v];
		for(int i = 0; diff; ++i, diff >>= 1)
			if(diff & 1) u = fa[i][u];

		for(int p = MaxL - 1; u != v; p ? --p : 0)
		{
			if(!p || fa[p][u] != fa[p][v])
			{
				u = fa[p][u];
				v = fa[p][v];
			}
		}

		return v;
	}

	int get_dist(int u, int v)
	{
		int lca = get_lca(u, v);
		return dist[u] + dist[v] - (dist[lca] << 1);
	}
} gp;

struct treap_t
{
	int val, size;
	treap_t *l, *r;
} treap_node[MaxS];
int treap_used;
treap_t *treap_nil;
std::stack<treap_t*> treap_mem;

treap_t *treap_newnode()
{
	if(!treap_mem.empty())
	{
		treap_t *n = treap_mem.top();
		treap_mem.pop();
		if(n->l != treap_nil)
 			treap_mem.push(n->l);
		if(n->r != treap_nil)
			treap_mem.push(n->r);
		return n;
	} else return treap_node + treap_used++;
}

void treap_insert(treap_t*& n, int v)
{
	if(n == treap_nil)
	{
		n = treap_newnode();
		*n = *treap_nil;
		n->size = 1; n->val = v;
	} else {
		++n->size;
		if(v < n->val)
		{
			treap_insert(n->l, v);
			if(n->l->size > n->r->size + 3)
			{
				// left rotate
				treap_t *q = n->l;
				n->l = q->r; q->r = n;
				q->size = n->size;
				n->size = n->l->size + n->r->size + 1;
				n = q;
			}
		} else {
			treap_insert(n->r, v);
			if(n->r->size > n->l->size + 3)
			{
				// right rotate
				treap_t *q = n->r;
				n->r = q->l; q->l = n;
				q->size = n->size;
				n->size = n->l->size + n->r->size + 1;
				n = q;
			}
		}
	}
}

int treap_find(treap_t* n, int v)
{
	int ans = 0;
	while(n != treap_nil)
	{
		if(v < n->val)
		{
			n = n->l;
		} else {
			ans += n->l->size + 1;
			n = n->r;
		}
	}
	return ans;
}

struct scape_t
{
	int size, top;
	scape_t *fa;
	treap_t *info, *parent_info;
} scape_node[MaxN];
scape_t *scape_nil;
int node_num, R[MaxN], depth[MaxN];
int mark_v, mark[MaxN], que[MaxN], fa[MaxN];
int size[MaxN], max_size[MaxN], dist[MaxN];
int record_num, record[MaxN];
long long lastans;

int bfs_sort(int u)
{
	int qhead = 0, qtail = 0;
	que[qtail++] = u;
	fa[u] = 0;
	while(qhead != qtail)
	{
		int u = que[qhead++];
		size[u] = max_size[u] = 0;
		for(int k = gp.head[u]; k; k = gp.next[k])
		{
			int v = gp.point[k];
			if(mark[v] == mark_v && fa[u] != v)
			{
				fa[v] = u;
				que[qtail++] = v;
			}
		}
	}

	return qtail;
}

scape_t* divide(int r, scape_t *f, int dep)
{
	int tot = bfs_sort(r);
	for(int i = tot - 1; i >= 0; --i)
	{
		int u = que[i];
		size[u] += 1;
		size[fa[u]] += size[u];
		if(max_size[fa[u]] < size[u])
			max_size[fa[u]] = size[u];
	}

	int root, root_size = ~0u >> 1;
	for(int i = 0; i != tot; ++i)
	{
		int u = que[i];
		if(max_size[u] < size[r] - size[u])
			max_size[u] = size[r] - size[u];
		if(max_size[u] < root_size)
			root = u, root_size = max_size[u];
	}

	dist[r] = 0;
	for(int i = 0; i != tot; ++i)
	{
		int u = que[i];
		for(int k = gp.head[u]; k; k = gp.next[k])
		{
			int v = gp.point[k];
			if(fa[u] != v && mark[v] == mark_v)
				dist[v] = dist[u] + gp.weight[k];
		}
	}

	tot = bfs_sort(root);
	mark[root] = 0; depth[root] = dep;
	scape_t *n = scape_node + root;
	n->fa = f; n->top = r; n->size = tot;

	for(int i = 0; i != tot; ++i)
		treap_insert(n->parent_info, dist[que[i]] - R[que[i]]);
	treap_insert(n->info, -R[root]);

	for(int k = gp.head[root]; k; k = gp.next[k])
	{
		int v = gp.point[k];
		if(mark[v] == mark_v)
		{
			scape_t *son = divide(v, n, dep + 1);
			int qhead = 0, qtail = 0;
			que[qtail++] = son->parent_info - treap_node;
			while(qhead != qtail)
			{
				treap_t *z = treap_node + que[qhead++];
				treap_insert(n->info, z->val + gp.weight[k]);
				if(z->l != treap_nil)
					que[qtail++] = z->l - treap_node;
				if(z->r != treap_nil)
					que[qtail++] = z->r - treap_node;
			}
		}
	}

	return n;
}

void scape_rebuild(scape_t *n)
{
	int qhead = 0, qtail = 0;
	int id = n - scape_node;
	que[qtail++] = id;
	mark[id] = ++mark_v;
	while(qhead != qtail)
	{
		int u = que[qhead++];
		treap_mem.push(scape_node[u].info);
		treap_mem.push(scape_node[u].parent_info);
		scape_node[u].info = treap_nil;
		scape_node[u].parent_info = treap_nil;
		for(int k = gp.head[u]; k; k = gp.next[k])
		{
			int v = gp.point[k];
			if(depth[v] > depth[id] && mark[v] != mark_v)
				que[qtail++] = v, mark[v] = mark_v;
		}
	}

	int dep = depth[n - scape_node];
	divide(n->top, n->fa, dep);
}

void scape_insert(int n, int fa, int dist, int r)
{
	// set tree info
	R[n] = r;
	gp.add_child(n, fa, dist);

	// set split info
	depth[n] = depth[fa] + 1;

	// init node
	scape_t *z = scape_node + n;
	*z = *scape_nil;
	z->size = 1; z->top = n;
	z->fa = scape_node + fa;
	treap_insert(z->info, -r);
	treap_insert(z->parent_info, -r);

	scape_t *unbalanced_node;
	double unbalanced_val = 0.0;

	// update chain
	for(scape_t *prev = z, *now = z->fa; now != scape_nil; prev = now, now = now->fa)
	{
		++now->size;
		// balance size
		if(double(prev->size) / now->size > unbalanced_val)
		{
			unbalanced_node = now;
			unbalanced_val = double(prev->size) / now->size;
		}

		// calc answer
		int d = gp.get_dist(now - scape_node, n);
		treap_insert(now->info, d - r);

		int dz = gp.get_dist(now->top, n);
		treap_insert(now->parent_info, dz - r);

		int id = now - scape_node;
		lastans += treap_find(now->info, r - d);

		int dn = gp.get_dist(prev->top, now - scape_node);
		lastans -= treap_find(prev->parent_info, r - d - dn);
	}

	if(unbalanced_val > alpha)
		scape_rebuild(unbalanced_node);
}

void init()
{
	treap_nil = treap_node + treap_used++;
	treap_nil->l = treap_nil->r = treap_nil;
	treap_nil->size = 0;

	scape_nil = scape_node;
	scape_nil->fa = scape_nil;
	scape_nil->info = treap_nil;
	scape_nil->parent_info = treap_nil;
	scape_nil->size = 0;
}

int main()
{
	int n;
	std::scanf("%*d %d", &n);
	init();
	for(int i = 1; i <= n; ++i)
	{
		int a, b, r;
		std::scanf("%d %d %d", &a, &b, &r);
		a ^= lastans % 1000000000;
		scape_insert(i, a, b, r);
		std::printf("%lld\n", lastans);
	}
	return 0;
}