P3899 [湖南集训]更为厉害 题解
题面
题目中条件等价于给你一个点 \(a\)，\(b\) 和 \(a\) 的深度差不能超过 \(w\)，\(c\) 要同时在 \(a\) 和 \(b\) 的子树中。
考虑分类讨论：
若 \(b\) 是 \(a\) 的祖先，那么答案为 \(\min(dep_a-1,w)\times (siz_a-1)\)；
若 \(b\) 在 \(a\) 的子树内，那么答案为 \(\sum_{dep_b\leq dep_a+w,b\in zishu(a)} (siz_b-1)\)。这个东西可以使用动态开点权值线段树维护，下标表示 \(dep\)，这样每个点的线段树可以把儿子的所有线段树合并起来得到，复杂度 \(O(n\log n)\)。
点击查看代码
#include
#include
inline int min(const int &a,const int &b){return a9)wt(x/10);putchar(x%10+'0');}
const int N=3e5+13,logN=20;
struct Edge{int v,nxt;}e[N<<1];
int n,q,h[N],tot,dep[N],siz[N],rt[N];
struct SegTree{int ls,rs;ll sum;}t[N*logN];
int pcnt;
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define mid ((l+r)>>1)
inline void refresh(int p){t[p].sum=t[ls(p)].sum+t[rs(p)].sum;}
void update(int &p,int l,int r,int x,int k){
if(!p) p=++pcnt;
if(l==r) return t[p].sum+=k,void();
x<=mid?update(ls(p),l,mid,x,k):update(rs(p),mid+1,r,x,k);
refresh(p);
}
int merge(int p,int q,int l,int r){
if(!p||!q) return p|q;
int x=++pcnt;
if(l==r) return t[x].sum=t[p].sum+t[q].sum,x;
ls(x)=merge(ls(p),ls(q),l,mid);
rs(x)=merge(rs(p),rs(q),mid+1,r);
return refresh(x),x;
}
ll query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return t[p].sum;
ll res=0;
if(L<=mid) res+=query(ls(p),l,mid,L,R);
if(R>mid) res+=query(rs(p),mid+1,r,L,R);
return res;
}
#undef mid
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs(int u,int fa){
dep[u]=dep[fa]+1,siz[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
dfs(v,u);siz[u]+=siz[v];
}
update(rt[u],1,n,dep[u],siz[u]-1);
if(fa) rt[fa]=merge(rt[fa],rt[u],1,n);
}
int main(){
n=rd(),q=rd();
for(int i=1;i