题解 P3899 【[湖南集训]谈笑风生】

# 线段树合并只打12分可太难了TvT 看来好多红名巨佬都跟我一样是从12分改过来的，其实是因为合并u点的线段树的时候把儿子的线段树信息给改了，那本蒟蒻就主要说说动态开点线段树的深度理解。 ## sol 首先看如果b和a没有祖先后代关系，a和b肯定不能同时是c的祖先，不成立； 如果b是a的祖先，方案数就是$\min(K,depth[a]-1)*(size[a]-1)$; 如果b是a的后代，方案数就是深度在depth[a]+1到depth[a]+K之间每个b的(size[b]-1)之和，那么可以用线段树合并来做，线段树下标表示深度，记区间的(size-1)之和，求线段树在(depth[a]+1,depth[a]+K)的区间和。 但是merge函数如果这么写的话（没新开节点，直接更新x的信息）就会获得12分的好成绩TvT： ```cpp int merge(int x,int y,int tl,int tr) { if(x==0||y==0) return x|y;//有空节点。 if(tl==tr) { tree[x].num=tree[x].num+tree[y].num; return x; } int mid=(tl+tr)/2; tree[x].ls=merge(tree[x].ls,tree[y].ls,tl,mid); tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr); up(x);//上传维护值。 return x; } ``` 只有新开了线段树节点才能A： ```cpp int merge(int x,int y,int tl,int tr) { if(x==0||y==0) return x|y;//有空节点。 if(tl==tr) { int now=++tot; tree[now].num=tree[x].num+tree[y].num; return now; } int mid=(tl+tr)/2,now=++tot;//为了不改变儿子线段树的值，必须新建节点。 tree[now].ls=merge(tree[x].ls,tree[y].ls,tl,mid); tree[now].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr); up(now); return now; } ``` 所以本篇题解详细讲一下产生这种情况的原因。 ## 线段树合并  要合并x和y两颗线段树，如果直接合并的话，x上的1号点右儿子直接赋成y上的2号点了，这样的话，x再和另一颗线段树合并，有可能改变2号点以及2号点子树的信息，y的信息就被乱改了。ovo 如果每次要合并的时候都给x新开一个节点，y的信息就不会被乱改了，每个点合并之后儿子的信息还是准确的。$*v*$ 但是x线段树递归到某个空子树的时候，还是要把y上对应的子树拿过来，这可以相当于是打标记，暂时用了y的子树。正经合并的时候肯定是不能改变y的信息了。 这样就能A掉这道题了…… ```cpp #include<bits/stdc++.h> using namespace std; const int mv=3e5,ml=19; int n,q; struct node{ int ls,rs; long long num;//每个点的siz-1之和。 }tree[2*mv*ml+3];int tot=0; inline void up(int x) { tree[x].num=tree[tree[x].ls].num+tree[tree[x].rs].num; } void add(int x,int tl,int tr,int w,int ad) { if(tl==tr) { tree[x].num+=ad; return; } int mid=(tl+tr)/2; if(w<=mid) { if(!tree[x].ls) tree[x].ls=++tot; add(tree[x].ls,tl,mid,w,ad); } if(w>mid) { if(!tree[x].rs) tree[x].rs=++tot; add(tree[x].rs,mid+1,tr,w,ad); } up(x); } long long askS(int x,int tl,int tr,int l,int r) { if(!x) return 0; if(tl==l&&r==tr) return tree[x].num; int mid=(tl+tr)/2;long long ans=0; //没建出来的地方值肯定为0，不用递归。 if(l<=mid&&tree[x].ls) ans+=askS(tree[x].ls,tl,mid,l,min(mid,r)); if(r>mid&&tree[x].rs) ans+=askS(tree[x].rs,mid+1,tr,max(l,mid+1),r); return ans; } int merge(int x,int y,int tl,int tr) { if(x==0||y==0) return x|y;//有空的则返回非空的。 if(tl==tr) { int now=++tot; tree[now].num=tree[x].num+tree[y].num; return now; } int mid=(tl+tr)/2,now=++tot;//为了不改变儿子线段树的值，必须新建节点。 tree[now].ls=merge(tree[x].ls,tree[y].ls,tl,mid); tree[now].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr); up(now); return now; } vector<int>po[mv+3]; int fa[mv+3],h[mv+3],siz[mv+3],rtw[mv+3]; //父亲、深度、子树大小、该点对应线段树树根的编号。 void dfs(int u) { siz[u]=1; for(int j=0;j<(int)po[u].size();j++) { int v=po[u][j]; if(fa[u]==v) continue; fa[v]=u; h[v]=h[u]+1; dfs(v); siz[u]+=siz[v]; } rtw[u]=++tot; add(rtw[u],1,n,h[u],siz[u]-1);//在线段树深度为h处加答案。 for(int j=0;j<(int)po[u].size();j++) { int v=po[u][j]; if(fa[u]==v) continue; rtw[u]=merge(rtw[u],rtw[v],1,n);//合并。 } } int main() { cin>>n>>q; int u,v; for(int e=1;e<n;e++) { scanf("%d%d",&u,&v); po[u].push_back(v); po[v].push_back(u); } h[1]=1;//深度从1开始记。 dfs(1); int K; for(int z=1;z<=q;z++) { scanf("%d%d",&u,&K); long long ans=1ll*min(h[u]-1,K)*(siz[u]-1);//上方谈笑风生。 ans+=askS(rtw[u],1,n,h[u]+1,h[u]+K);//下方谈笑风生。 printf("%lld\n",ans); } return 0; } ```