[题解] 紫荆花之恋

题目大意是

一棵树，动态加点，边有边权点有点权r[i]

一个点对(x,y)合法的条件是r[x]+r[y]>=dis(x,y)，求每次加点后的合法点对数

题解

每次加点后计算新产生的点对数，是 x 点和[1,x-1]内的点

考虑点分树，d[i]表示 i 到当前分治中心的距离

然后暴力跳 x 的父亲，一个容斥，用分治中心 u 的子树内的合法数量减去u的儿子且是x的祖先的合法数量

用平衡树维护每个分治中心的d[j]-r[j]

由于动态加点，点分树采取替罪羊树的思想重构

题解写完了，但是不难发现这个题更重要的是实现过程

分别检查了替罪羊树，倍增，跳父亲求答案的函数，在点分树重构的地方花了很多时间

分别写基本不会错，掺一块儿就觉得很恶心，好像注意力被分散了，也可能是我自身对大码量题目的抵触(其实1.7k就行？？？)，，，

调的时候发现平时根本不会写错的倍增竟然错了两处，还是分两次发现的

都是些零散的细节，比如我要重构x在点分树上的子树，要先断掉fa[x]->x的边，然后再用root和fa[x]连边，可是我忘记断了就出环了

再比如，我要建出点分树同时更新其每个节点的平衡树，跳到根或其父亲就不能跳了，因为祖先的平衡树没有清空

还有一个地方，我是跳父亲更新平衡树的，所以点分治时要先建边再分治到下一层

各自都是些很容易想到和规避的问题，但是同时出现就不是很容易考虑到了

所以先想好细节再码是必要的，但是对于细节很多的题还是不太能全部想到

所以去写大模拟吧，猪国杀.杀蚂蚁.鸭棋都是不错的题呢，，，，

代码

#include
using namespace std;
#define il inline
const int N=1e5+11;
const int M=N*150;
const double alp=0.7;
int n,now;
int r[N];
int sum[N],c[N];
int dep[N],pg[N];
int st[19][N];
vector vct[N];
il int max_(int x,int y){return x>y?x:y;}
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void init_x(int x,int fa){
	if(fa)vct[x].push_back(fa),vct[fa].push_back(x);
	sum[x]=sum[fa]+c[x];
	dep[x]=dep[fa]+1,st[0][x]=fa;
	for(int i=1;i<=pg[dep[x]];++i)st[i][x]=st[i-1][st[i-1][x]];
}
int get_lca(int x,int y){
	if(dep[x]=0;--i)if(dep[st[i][x]]>=dep[y])x=st[i][x];
	if(x==y)return x;
	for(int i=pg[dep[x]];i>=0;--i)if(st[i][x]!=st[i][y])x=st[i][x],y=st[i][y];
	return st[0][x];
}
int get_dis(int x,int y){return sum[x]+sum[y]-2*sum[get_lca(x,y)];}
struct sgt_{
	int f,rb;
	int sta[M],top;
	int que[M],tp,tot;
	int siz[M],cnt[M],val[M];
	int ch[M][2];
	il int New(int x){int k=tp?que[tp--]:++tot;siz[k]=cnt[k]=1,val[k]=x;return k;}
	void dfs(int x){if(!x)return;dfs(ch[x][0]),sta[++top]=x,dfs(ch[x][1]);}
	il bool bad(int x){return siz[x]>=1&&(1.0*siz[ch[x][0]]/siz[x]>=alp||1.0*siz[ch[x][1]]/siz[x]>=alp);}
	void init(int x){
		top=0;dfs(x);
		for(int k,i=1;i<=top;++i){
			que[++tp]=k=sta[i];
			ch[k][0]=ch[k][1]=0;
			siz[k]=cnt[k]=val[k]=0;
		}
	}
	int build(int l,int r){
		if(l>r)return 0;
		int mid=(l+r)>>1,x=sta[mid];
		siz[x]=cnt[x]+siz[ch[x][0]=build(l,mid-1)]+siz[ch[x][1]=build(mid+1,r)];
		return x;
	}
	int rebuild(){top=0,dfs(rb);return build(1,top);}
	void ins_(int &i,int x,int fa){
		if(!i){i=New(x);return;}++siz[i];++now;
		if(val[i]==x){++cnt[i];return;}
		if(xe[N];
	bool bad(int x){return siz[x]>=1&&(1.0*siz[x]/siz[f[x]])>=alp;}
	void add(int x,int y){if(!x)return;e[x].insert(y),e[y].insert(x);f[y]=x;}
	void init(int i){
		e[i].clear();
		sgt.init(rt1[i]),sgt.init(rt2[i]);
		rt1[i]=rt2[i]=0;
		siz[i]=f[i]=0;jud[i]=0;
	}
	void dfs(int x,int fa){
		for(int v : e[x])if(v!=fa)dfs(v,x);init(x);
	}
	void get_rt(int x,int fa,int now){
		siz[x]=1;int mx=0;
		for(int v : vct[x]){
			if(jud[v]||v==fa)continue;
			get_rt(v,x,now);
			siz[x]+=siz[v];
			mx=max_(mx,siz[v]);
		}if((mx=max_(mx,now-siz[x]))