【线段树】[LUOGU [湖南集训] 谈笑风生]线段树合并

本文主要是介绍【线段树】[LUOGU [湖南集训] 谈笑风生]线段树合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目:

题目链接：[LUOGU [湖南集训] 谈笑风生]
题解：
由于是要求符合条件的三元组，那么可以分成两段来写，

第一段：如果b在a的上面的时候
在这一段中c就可以是a的子树大小，而b的话就是 $m i n (d e e p [a] - 1, K)$ ，这一部分的答案就是 $s i z e [a] * m i n (d e e p [a] - 1, K)$

第二段：如果b在a的下面的时候
在这一段中就是 $(d e e p [x] + 1, d e e p [x] + k)$ 之间的答案累计。对于每个点都建一个权值线段树，以 $d e e p$ 为点权值对子树大小 $s i z e$ 进行答案合并，然后查找出 $(d e e p [x] + 1, d e e p [x] + k)$ 之间的答案即可。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=3e5+7;
struct hit{LL size;int deep,ls,rs;}tr[sea*40];
struct see{int ver,next;}e[sea<<1];
int n,m,tot,sz,cnt,seg,root[sea],last[sea],siz[sea];
void add(int x,int y){e[++tot].ver=y;e[tot].next=last[x];last[x]=tot;}
void build(int &k,int l,int r,int val,int tt)
{if(!k) k=++seg; tr[k].size+=tt;if(l==r) return; int mid=(l+r)/2;if(val<=mid) build(tr[k].ls,l,mid,val,tt);else build(tr[k].rs,mid+1,r,val,tt);
}
int incor(int x,int y,int l,int r)
{if(!x||!y)return x|y ;int mid=(l+r)/2,k=++seg;tr[k].size=tr[x].size+tr[y].size;tr[k].ls=incor(tr[x].ls,tr[y].ls,l,mid);tr[k].rs=incor(tr[x].rs,tr[y].rs,mid+1,r);return k;
}
LL ask(int L,int R,int l,int r,int x)
{if(!x)return 0;if(L<=l&&r<=R)return tr[x].size;int mid=l+r>>1;LL res=0;if(mid>=L) res+=ask(L,R,l, mid ,tr[x].ls);if(mid< R) res+=ask(L,R,mid+1,r,tr[x].rs);return res;
}
void dfs(int x,int fa=0)
{tr[x].deep=tr[fa].deep+1; siz[x]=1;for(int i=last[x];i;i=e[i].next)if(e[i].ver!=fa) dfs(e[i].ver,x),siz[x]+=siz[e[i].ver];build(root[x],1,sz,tr[x].deep,siz[x]-1);if(fa) root[fa]=incor(root[fa],root[x],1,sz);
}
int main()
{     n=read();  m=read();sz=n;for(int i=1,x,y;i<n;i++) x=read(),y=read(),add(x,y),add(y,x); dfs(1);for(int i=1;i<=m;i++) {int x=read(),k=read();printf("%lld\n",ask(tr[x].deep+1,tr[x].deep+k,1,n,root[x])+1LL*(siz[x]-1)*min(tr[x].deep-1,k));}return 0;
}