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;
}