【LG-P3920/WC2014】 紫荆花之恋
pldzy
2022-06-02 13:23:58
# Solution
在此提供一种可能相对其他解法~~较为好写~~的做法。
## 一
首先考虑一棵如下图的树，其中 $rtlr_0=6,\ rtlr_1=5$。
发现此时这棵树不考虑根节点只有两条链，而左右链的末尾分别是 $rtlr_0$ 和 $rtlr_1$。
同时，~~按照套路~~，我们将 $dist(i,j) \leq r_i+r_j$ 化为 $dist(i, l)-r_i\leq r_j-dist(j,l)$，其中 $l$ 为 $i$ 和 $j$ 的最近公共祖先。
对于上图，我们只用维护 4 棵平衡树（使用平衡树因为我们是在维护在某一集合内比某数要大的值的个数）就可以把答案求出，具体实现如下：
```cpp
inline void add(int u, int v, int w){
e[++cnt] = (edge){v, hd[u], w}, hd[u] = cnt;
e[++cnt] = (edge){u, hd[v], w}, hd[v] = cnt;
}
inline void rotate(int &x, int k){
int y = t[x].ch[k];
t[x].ch[k] = t[y].ch[!k], t[y].ch[!k] = x;
t[y].s = t[x].s,
t[x].s = t[t[x].ch[1]].s + t[t[x].ch[0]].s + 1;
x = y;
}
inline void insrt(int &x, int v){
if(!x){
x = ++tot;
t[x].s = 1, t[x].a = v;
return;
}
bool k = (v >= t[x].a);
insrt(t[x].ch[k], v), t[x].s += 1;
if(t[x].s * 0.8 < t[t[x].ch[k]].s)
rotate(x, k);
}
inline int query(int x, int v){
if(!x) return 0;
if(v <= t[x].a)
return query(t[x].ch[0], v) + t[t[x].ch[1]].s + 1;
else return query(t[x].ch[1], v);
}
int main(){
rd(), n = rd(), rd(), rd(), val[1] = rd();
rtlr[0] = rtlr[1] = 1;
printf("0\n");
insrt(rt1[0], val[1]), insrt(rt1[1], val[1]);//rt1/2[0]维护左边的分支
insrt(rt2[0], val[1]), insrt(rt2[1], val[1]);//rt1/2[1]维护右边的分支
for(i = 2; i <= n; ++i){
f[i] = rd() ^ ans % mod, j = rd(), val[i] = rd();
if(f[i] != rtlr[1] and f[i] != rtlr[0]) break;//如果此时不满足只有两条链的形态，就 break 掉
add(i, f[i], j);
dis[i] = dis[f[i]] + j;//dis[i] 为 i 到根节点的距离
fx = (f[i] == rtlr[1])/*看 i 在左右哪条链上*/, rtlr[fx] = i;
ans += query(rt1[fx], dis[i] - val[i]) + query(rt2[!fx], dis[i] - val[i]);
if(dis[i] <= val[1] + val[i]) ans -= 1;//减去重复计算的
insrt(rt1[fx], dis[i] + val[i]), insrt(rt2[fx], val[i] - dis[i]);//rt1和rt2分别插入不同的值，辅助求解答案
printf("%lld\n", ans);
}
}
```
## 二
然后我们再来考虑当树的形态不满足上面的要求时，如下图：
### 1. 求解答案
面对这种情况，我们对于每个点要维护两棵平衡树：
一棵用于记录以当前节点 $i$ 为根的树内每个子节点 $j$ 的 $r_j-dist(j, fa_i)$ 的值，这棵平衡树的根的编号记为 $ms_i$；
一棵用于记录当前节点 $i$，它其中一个儿子 $j$，$j$ 子树内的所有子节点 $k$ 的 $r_k-dist(k,i)$ 的值，记为 $gs_i$（注意 $gs_i$ 中并没有记录 $i$ 的直接儿子 $j$ 的信息）。
对于每个节点，我们再去维护它分别到每一个深度的祖先的距离，对于第 $k$ 层的祖先，节点 $i$ 到它的距离记为 $adis_{k,i}$。
然后我们试着去求一下对于新增的一个节点 $i$，最终答案是多少。
过程如下：
```cpp
for(k = dep[f[i]], l = f[i], o = i; l; k--, o = l, l = f[l])
u = adis[k][i] - val[i],
ans += query(gs[l], u) - query(ms[o], u);
```
我们从下往上去遍历每一个祖先，对于每一个祖先，我们利用刚刚对每个节点维护的两棵平衡树进行求解答案。
### 2. 添加新节点
然后我们就考虑如何把这个节点加入这棵树内。
首先，肯定是按照刚刚求答案那样，从下往上去遍历祖先，对于每一个祖先，我们分别在它的两棵平衡树内插入新节点的信息即可。
但是如果单单只是这样，树的深度就可能会无止境地增加，这绝不是我们想要的。
~~所以这时候就要请出替罪羊树了！~~ 我们用替罪羊树的思路，在从下往上遍历祖先的同时，去检查每棵子树的大小有没有超过其父亲子树大小的 0.88 倍。
如果有，就把它记录下来，然后就对它进行重构。
重构一棵树的步骤：
1. “拍扁”这棵树，然后选出一个大小刚刚好超过或等于总节点数一半的节点，把它当做新根。
2. 对于这个新根，我们去建立它的新平衡树，然后对它的每一个儿子，重复第 1 和 2 步。
然后这道题就结束了，复杂度可过。
虽然~~口胡~~起来并不复杂，但是代码实现的时候还是需要注意很多细节的。
# Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int mod = 1000000000;
inline int rd(){
int x = 1, s = 0;
char ch = getchar();
while(ch < '0' or ch > '9'){
if(ch == '-') x = -1;
ch = getchar();
}
while(ch >= '0' and ch <= '9')
s = s * 10 + ch - '0', ch = getchar();
return s * x;
}
struct tree{
int s, a;
int ch[2];
}t[maxn * 200];
bool fx;
int rt1[2], rt2[2], rtlr[2];
int n, m, i, j, k, l, o, u, v;
int val[maxn], f[maxn];
int cnt, hd[maxn];
struct edge{
int to, nxt, w;
}e[maxn << 1];
int tsiz[maxn], siz[maxn], in[maxn], id[maxn];
int gs[maxn], ms[maxn];
int dep[maxn], dis[maxn], adis[100][maxn];
int pre[maxn], he, ta, que[maxn];
int tot;
ll ans;
inline void add(int u, int v, int w){
e[++cnt] = (edge){v, hd[u], w}, hd[u] = cnt;
e[++cnt] = (edge){u, hd[v], w}, hd[v] = cnt;
}
inline void rotate(int &x, int k){
int y = t[x].ch[k];
t[x].ch[k] = t[y].ch[!k], t[y].ch[!k] = x;
t[y].s = t[x].s,
t[x].s = t[t[x].ch[1]].s + t[t[x].ch[0]].s + 1;
x = y;
}
inline void insrt(int &x, int v){
if(!x){
x = ++tot;
t[x].s = 1, t[x].a = v;
return;
}
bool k = (v >= t[x].a);
insrt(t[x].ch[k], v), t[x].s += 1;
if(t[x].s * 0.8 < t[t[x].ch[k]].s)
rotate(x, k);
}
inline int query(int x, int v){
if(!x) return 0;
if(v <= t[x].a)
return query(t[x].ch[0], v) + t[t[x].ch[1]].s + 1;
else return query(t[x].ch[1], v);
}
inline int fndrt(int x, int tdep, int tdis, int fa){
int i, j, k;
he = ta = 0;
que[ta++] = x, dis[x] = tdis;
pre[x] = 0;
while(he != ta){
i = que[he++];
dep[i] = tdep + 1, tsiz[i] = 1;
for(j = hd[i]; j; j = e[j].nxt){
k = e[j].to;
if(k != pre[i] and dep[k] >= tdep)
que[ta++] = k, pre[k] = i,
dis[k] = dis[i] + e[j].w;
}
if(tdep) adis[tdep - 1][i] = dis[i];
}
for(i = ta - 1; i >= 0; --i){
k = pre[que[i]];
tsiz[k] += tsiz[que[i]];
if(tsiz[que[i]] * 2 >= ta) break;
}
j = que[i], f[j] = fa, siz[j] = ta, dep[j] = tdep;
if(tdep) in[j] = x, id[j] = tdis;
else in[j] = id[j] = 0;
return j;
}
inline void build(int x){
int i, j, k, l, o;
adis[dep[x]][x] = gs[x] = 0;
insrt(gs[x], val[x]);
for(i = hd[x], j = e[i].to; i; i = e[i].nxt, j = e[i].to){
if(dep[j] < dep[x]) continue;
k = fndrt(j, dep[x] + 1, e[i].w, x);
ms[k] = 0;
for(l = 0; l < siz[k]; ++l){
o = que[l];
insrt(gs[x], val[o] - dis[o]);
insrt(ms[k], val[o] - dis[o]);
}
build(k);
}
}
inline void calc(int i){
add(i, f[i], j);
dep[i] = dep[f[i]] + 1, siz[i] = 1,
in[i] = i, id[i] = j;
insrt(gs[i], val[i]);
for(k = 0; k < dep[i]; ++k)
adis[k][i] = adis[k][f[i]] + j;
for(k = dep[f[i]], l = f[i], o = i; l; k--, o = l, l = f[l])
u = adis[k][i] - val[i],
ans += query(gs[l], u) - query(ms[o], u);
printf("%lld\n", ans);
for(k = dep[f[i]], v = 0, l = f[i], o = i; l; k--, o = l, l = f[l]){
u = val[i] - adis[k][i];
insrt(gs[l], u), insrt(ms[o], u);
siz[l] += 1;
if(siz[l] * 0.88 < siz[o]) v = l;
}
if(v){
if(dep[v]) u = fndrt(in[v], dep[v], id[v], f[v]);
else u = fndrt(1, 0, 0, 0);
ms[u] = ms[v], ms[v] = 0;
build(u);
}
}
int main(){
rd(), n = rd(), rd(), rd(), val[1] = rd();
rtlr[0] = rtlr[1] = 1;
printf("0\n");
insrt(rt1[0], val[1]), insrt(rt1[1], val[1]);
insrt(rt2[0], val[1]), insrt(rt2[1], val[1]);
for(i = 2; i <= n; ++i){
f[i] = rd() ^ ans % mod, j = rd(), val[i] = rd();
if(f[i] != rtlr[1] and f[i] != rtlr[0]) break;
add(i, f[i], j);
dis[i] = dis[f[i]] + j;
fx = (f[i] == rtlr[1]), rtlr[fx] = i;
ans += query(rt1[fx], dis[i] - val[i]) + query(rt2[!fx], dis[i] - val[i]);
if(dis[i] <= val[1] + val[i]) ans -= 1;
insrt(rt1[fx], dis[i] + val[i]), insrt(rt2[fx], val[i] - dis[i]);
printf("%lld\n", ans);
}
if(i > n) return 0;
for(k = 1; k <= tot; ++k)
t[k].ch[0] = t[k].ch[1] = 0;
tot = 0, memset(dis, 0, sizeof dis);
k = fndrt(1, 0, 0, 0), build(k);
for(calc(i), i += 1; i <= n; ++i)
f[i] = rd() ^ ans % mod, j = rd(), val[i] = rd(), calc(i);
return 0;
}
```
------------
感谢阅读。
辛苦管理员审核，若有问题烦请指出。