JSK42586.Tree（动态开点线段树+树上启发式合并）

题意：

给定一颗n个节点的树。每个点有点权(v_i)，询问有序对((x,y))使得：

1. x不是y的祖先，且y不是x的祖先。
2. x和y的简单路径之和不超过k。
3. x和y的点权满足：(v_x+v_y=2v_{lca(x,y)})

题解：

假设当前枚举的点为(x)，子树根节点为(u)。

需要找的点(y)需要满足的条件是：

(v_y=2v_u-v_x,1 leq d_y leq k+2d_u-d_y)

对每个权值建一颗动态开点线段树，然后根据(d)的范围查询点对。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
const int M=1e5;
typedef long long ll;
int n,k;
vector<int> g[maxn];
ll ans;
int L[maxn],R[maxn],id[maxn],tot;

int sz[maxn],dep[maxn],son[maxn],a[maxn];
int T[maxn],sum[maxn*100],lson[maxn*100],rson[maxn*100],tol;

void up (int &rt,int pos,int L,int R,int v) {
	if (!rt) rt=++tol;
	sum[rt]+=v;
	if (L==R) return;
	int mid=(L+R)>>1;
	if (pos<=mid) up(lson[rt],pos,L,mid,v);
	if (pos>mid) up(rson[rt],pos,mid+1,R,v);
}
int query (int rt,int l,int r,int L,int R) {
	if (!rt) return 0;
	if (L<=l&&r<=R) return sum[rt];
	int mid=(l+r)>>1;
	int ans=0;
	if (L<=mid) ans+=query(lson[rt],l,mid,L,R);
	if (R>mid) ans+=query(rson[rt],mid+1,r,L,R);
	return ans; 
}

void dfs1 (int u,int pre) {
	L[u]=++tot;
	id[tot]=u;
	sz[u]=1;
	for (int v:g[u]) {
		if (v==pre) continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		sz[u]+=sz[v];
		if (sz[v]>sz[son[u]]) son[u]=v; 
	}
	R[u]=tot;
}
void dfs2 (int u,int pre,int kp) {
	for (int v:g[u]) {
		if (v==pre||v==son[u]) continue;
		dfs2(v,u,0); 
	}
	if (son[u]) dfs2(son[u],u,1);
	
	for (int v:g[u]) {
		if (v==pre||v==son[u]) continue;
		for (int j=L[v];j<=R[v];j++) {
			int tt=id[j];
			int rt=2*a[u]-a[tt];
			int r=k+2*dep[u]-dep[tt];
			if (rt>=0&&rt<=M&&r>=1) ans+=query(T[rt],0,M,0,r);
		}
		for (int j=L[v];j<=R[v];j++) {
			int tt=id[j];
			up(T[a[tt]],dep[tt],0,M,1);
		}
	}
	up(T[a[u]],dep[u],0,M,1);
	if (!kp) {
		for (int j=L[u];j<=R[u];j++) {
			int tt=id[j];
			up(T[a[tt]],dep[tt],0,M,-1);
		}
	}
}
int main () {
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",a+i);
	for (int i=2;i<=n;i++) {
		int x;
		scanf("%d",&x);
		g[x].push_back(i);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	printf("%lld
",ans*2); 
}