P3920 WC2014 紫荆花之恋
毒瘤题目，动态点分树。
前置科技点
- 替罪羊树
- 高速平衡树（除去
fhq_treap和splay之外的所有平衡树）
约定
\(dis(u,v)\) 为原树上 \(u,v\) 两点间的距离
\(siz\) 为子树大小
思路
维护一棵可以动态插入节点的点分树，有点权和边权，求任意两点点权和大于两点间路径边权和的节点对数。
强制在线（万恶之源）
part1:处理询问
如果把强制在线去掉，建点分树，这题是一个很经典的点分树可以维护的问题。
在点分树上某个节点 \(i\) 统计所有经过这个点连接的点对的个数：
\[r_u+r_v\geq dis(u,i)+dis(i,v) \]移项得：
\[-(dis(u,i)-r_u)\geq dis(i,v)-r_v \]枚举 \(u\)，沿着 \(u\) 在点分树上祖先，统计满足要求的 \(v\) 即可。
用平衡树维护，可以做到 \(O(\log n)\) 查询。
这里我们需要处理去重的问题，有哪些 \((u,v)\) 会在点分树上的父亲处再次统计一次。
设 \(i\) 的点分树上父亲为 \(f\)，我们需要把自己子树内的节点在父亲平衡树内储存的信息 copy 一份到 \(i\)，减去满足 \(-(dis(f,u)-r_u)\geq dis(v,f)-r_v\) 的点对数列。
这样下来，查询时间复杂度 \(\log^2 n\)。
part2:替罪羊树维护点分树
替罪羊树的思想使得替罪羊树保证了高度在 \(\log\) 以内的思想，我们用类似的思想维护点分树。
每次直接把节点接在父亲上，然后沿着点分树上的祖先检查是否有儿子节点的 \(siz*a\) 大于父亲节节点的 \(siz*b\)，直到找到最浅的一个满足这样关系的点，对其所在子树进行重构。
重构时，重置一些数组：
1.该子树内所有平衡树。
2.已加入点分树的标记。
3.点分树上所在子树的编号集数组。
4.点分树上的祖先数组（这个数组只需要清空连续的一部分，可以利用加入点分树的标记清空）。
Ps:按照笔者的习惯，祖先数组包括节点本身。
part3:点分树
最主要的过程竟然是最简单的。
构建点分树，点分树上的节点 \(u\)。
-
维护两个平衡树，设 \(u\) 的父亲为 \(f\)，\(v\) 为 \(u\) 的点分树上子树内的一个节点，第一个平衡树加入 \(dis(u,v)-r_v\) 第二个维护 \(dis(f,v)-r_v\)，供后面的求值操作使用。
-
维护已加入点分树标记。
-
维护祖先数组（这里的祖先数组使用
pair，first维护祖先标号，second维护距离）。 -
维护点分树上子树集数组。
part4:插入节点
插入一个节点 \(u\)，把他挂在他的父亲 \(f\) 上。
1.链式前向星加边。
2.将 \(f\) 的祖先数组复制下来，将 \(second\) 全部加上边权 \(w\)，最后加入自己。
3.更新祖先的点分树上子树集数组。
4.沿着祖先数组，更新两颗平衡树。
5.从最浅的祖先开始查找不合符要求的 \(siz\)，并对此节点的点分树子树进行重构。
节点 1 的插入需要特判。
关于平衡树
本题需要高速平衡树，但是我们可以用 pb_ds 库中的平衡树来代替，可以使用 pair 插入的方法消除不可以重复值的限制（第一位存值，第二位随机一个数）。
实测，替罪羊树 \(a\) 取 \(0.75\) 可以在该方法下通过此题。
代码
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mod 1000000000
#define F first
#define S second
const int maxn=1e5+5;
tree<pli, null_type, less<pli>, rb_tree_tag, tree_order_statistics_node_update> T1[maxn],T2[maxn];
int r[maxn];
struct Edge//链式前向星存边
{
int tot;
int head[maxn];
struct edgenode{int to,nxt;ll w;}edge[maxn*2];
inline void add(int x,int y,ll z)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
edge[tot].w=z;
head[x]=tot;
}
}T;
namespace VCD_tree
{
int rt;
int siz[maxn];
bool cut[maxn],book[maxn];//cut 为加入点分树标记
vector<pil>fa[maxn];//祖先数组
vector<int>ve[maxn];//点分树子树数组
inline void dfs_siz(int u)
{
book[u]=true;siz[u]=1;
for(int i=T.head[u];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(!book[v]&&!cut[v]) dfs_siz(v),siz[u]+=siz[v];
}
book[u]=false;
}
inline int dfs_rt(int u,const int tot)
{
book[u]=true;int ret=u;
for(int i=T.head[u];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(!book[v]&&!cut[v]&&siz[v]*2>=tot){ret=dfs_rt(v,tot);break;}
}
book[u]=false;return ret;
}
inline void dfs2(int u,const int f,ll dis)
{
book[u]=true;
int k=fa[u].size()-1;
if(k>=0) T2[f].insert({fa[u][k].S-r[u],rand()});T1[f].insert({dis-r[u],rand()});
fa[u].push_back({f,dis});ve[f].push_back(u);
for(int i=T.head[u];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(!book[v]&&!cut[v]) dfs2(v,f,dis+T.edge[i].w);
}
book[u]=false;
}
inline void solve(int u,int f)
{
dfs_siz(u);int g=dfs_rt(u,siz[u]);cut[g]=true;
int k=fa[g].size()-1;
if(k>=0) T2[g].insert({fa[g][k].S-r[g],rand()});T1[g].insert({-r[g],rand()});
fa[g].push_back({g,0});ve[g].push_back(g);
for(int i=T.head[g];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(!cut[v]){dfs2(v,g,T.edge[i].w);solve(v,g);}
}
}//以上为点分树基操
inline void rebuild(int p)//重构前清空
{
for(auto i:ve[p])
{
if(i==p) continue;
for(auto it1=fa[i].rbegin();it1->F!=p;it1=fa[i].rbegin()) fa[i].pop_back();
ve[i].clear();T1[i].clear();T2[i].clear();fa[i].pop_back();cut[i]=false;
}
for(auto it1=fa[p].rbegin();it1->F!=p;it1=fa[p].rbegin()) fa[p].pop_back();
ve[p].clear();T1[p].clear();T2[p].clear();fa[p].pop_back();cut[p]=false;
solve(p,0);
}
inline ll insert(int u,int f,ll w)//插入节点
{
if(!f)//特判
{
fa[u].push_back({u,0});ve[u].push_back(u);
T1[u].insert({-r[u],rand()});rt=u;
return 0;
}
T.add(u,f,w),T.add(f,u,w);
for(auto i:fa[f]) fa[u].push_back({i.F,i.S+w}),ve[i.F].push_back(u);
fa[u].push_back({u,0});ve[u].push_back(u);
ll lst=1e18;
for(auto i:fa[u])//更新平衡树
{
if(lst!=1e18) T2[i.F].insert({lst,rand()});
T1[i.F].insert({i.S-r[u],rand()});lst=i.S-r[u];
}
vector<pil>::iterator it1,it2;//查是否需要重构
for(it1=fa[u].begin(),it2=it1,it2++;it2!=fa[u].end();it1++,it2++)
if(ve[it1->F].size()*3<=ve[it2->F].size()*4){rebuild(it1->F);break;}
ll res=T1[u].order_of_key({r[u]+1,-1});//求答案
int t=fa[u].size()-1;
for(int i=fa[u].size()-2;i>=0;t=i,i--)
{
res+=T1[fa[u][i].F].order_of_key({-(fa[u][i].S-r[u])+1,-1});
res-=T2[fa[u][t].F].order_of_key({-(fa[u][i].S-r[u])+1,-1});
}
return res-1;//-1是要减去自己
}
inline void init(){memset(cut,1,sizeof(cut));}//初始化
}
ll lst;
int n;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
inline void write(ll X)
{
if(X<0) {X=~(X-1); putchar('-');}
if(X>9) write(X/10);
putchar(X%10+'0');
}
int main()
{
int _;scanf("%d",&_);
scanf("%d",&n);
VCD_tree::init();
for(int i=1;i<=n;i++)
{
int f,w;
f=read(),w=read(),r[i]=read();
f^=(lst)%mod;
lst+=VCD_tree::insert(i,f,w);
write(lst);putchar('\n');
}
}
166行，2 weeks，感觉身体被掏空。
标签：fa,int,紫荆花,back,edge,WC2014,P3920,点分,dis From： https://www.cnblogs.com/binbinbjl/p/18162622