2023NOIP A层联测26 T3 tour
有意思的树上主席树。
思路
首先考虑一个点 \(p\) 能计入答案的情况，就是 \(dis(x,p)-a_p \ge a_p\)。 我们把 \(x \to y\) 的路径拆成 \(x \to lca,lca \to y\) 两条。
记录一个点 \(x\) 到根路径上的前缀和为 \(s_x\)，对于两条路径，我们分类讨论：
第一条，合法条件为 \(s_x-s_p \ge a_p\)，也就是 \(s_p+a_p \le s_x\)。左边的是一个关于 \(p\) 的式子，我们把它放到某个数据结构里面，查询一条链上小于等于给定值的值的个数，如果树给定，这显然是可以通过主席树来做的。
具体来说，每个点继承它父亲的版本，最后把两个版本一减就好了。
第二条，我们记录 lca 的父亲为 \(z\)，那么合法条件为 \(s_x-s_z+s_p-s_{lca}-a_p \ge a_p\)，也就是 \(2 \times a_p-s_p \le s_x-s_z-s_{lca}\)。
左边是一个关于 \(p\) 的式子，右边是一个定值，也可以用类似的方法通过主席树求出。
那么允许离线的方法就很明显了，先建出树，然后对于每个点维护两棵主席树，分别表示第一种和第二种情况，然后查询的时候拆成两条路径分别查询即可（注意不要重复算 lca）。
现在考虑在线。一个经典的方法是启发式合并，由于答案和树的形态无关，可以每次把 size 小的连通块合并到 size 大的连通块上，对于 size 小的那个连通块，我们暴力重构需要维护的信息，包括倍增数组、前缀和数组和主席树。然后正常查询就好了。
启发式合并的复杂度是 \(O(n \log n)\)，再加上重构倍增数组和主席树，复杂度就是 \(O(n \log n \log V)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define lch(p) tree[p].ch[0]
#define rch(p) tree[p].ch[1]
const int maxm=5e7+10,maxn=1e5+5;
const int lim=5e8;
struct Tree
{
int ch[2],siz;
}S1[maxm],S2[maxm];
struct Edge
{
int to,nxt;
}edge[maxn*2];
int n,S1tot,S2tot,tot,tp,q,la;
int val[maxn],head[maxn],fa[maxn],sz[maxn],rt1[maxn],rt2[maxn],f[maxn][25],sum[maxn],dep[maxn];
void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
int findroot(int x){return fa[x]==x?x:fa[x]=findroot(fa[x]);}
void insert(Tree *tree,int &tot,int &p,int l,int r,int x)
{
tree[++tot]=tree[p];
p=tot;
if(l==r){tree[p].siz++;return ;}
int mid=l+r>>1;
if(mid>=x) insert(tree,tot,lch(p),l,mid,x);
else insert(tree,tot,rch(p),mid+1,r,x);
tree[p].siz=tree[lch(p)].siz+tree[rch(p)].siz;
}
int query(Tree *tree,int p,int lp,int l,int r,int lx,int rx)
{
if(lx<=l&&r<=rx) return tree[p].siz-tree[lp].siz;
if(rx<l||r<lx) return 0;
int mid=l+r>>1;
return query(tree,lch(p),lch(lp),l,mid,lx,rx)+query(tree,rch(p),rch(lp),mid+1,r,lx,rx);
}
void dfs(int u,int fa,int d)
{
dep[u]=d;
f[u][0]=fa;
for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
rt1[u]=rt1[fa],rt2[u]=rt2[fa];
sum[u]=sum[fa]+val[u];
insert(S1,S1tot,rt1[u],-lim,lim,sum[u]+val[u]);
insert(S2,S2tot,rt2[u],-lim,lim,2*val[u]-sum[u]);
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==fa) continue;
dfs(v,u,d+1);
}
}
int Lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=20;i>=0;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(u==v) return u;
for(int i=20;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return f[u][0];
}
int main()
{
scanf("%d",&tp);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
fa[i]=i,sz[i]=1,sum[i]=val[i],dep[i]=1;
insert(S1,S1tot,rt1[i],-lim,lim,val[i]*2);
insert(S2,S2tot,rt2[i],-lim,lim,val[i]);
}
while(q--)
{
int op,u,v;
scanf("%d%d%d",&op,&u,&v);
if(tp) u=u^la,v=v^la;
if(!op)
{
int fu=findroot(u),fv=findroot(v);
if(sz[fu]<sz[fv]) swap(u,v),swap(fu,fv);
fa[fv]=fu,sz[fu]+=sz[fv];
dfs(v,u,dep[u]+1);
add(u,v);
add(v,u);
}
else
{
int lca=Lca(u,v);
int z=f[lca][0];
la=query(S1,rt1[u],rt1[z],-lim,lim,-lim,sum[u])+query(S2,rt2[v],rt2[lca],-lim,lim,-lim,sum[u]-sum[lca]-sum[z]);
printf("%d\n",la);
}
}
}