设 T 为一棵有根树，我们做如下的定义：

• 设 a 和 b 为 T 中的两个不同节点。如果 a 是 b 的祖先，那么称“a 比 b 不知道高明到哪里去了”。

• 设 a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数 x，那么称“a 与 b 谈笑风生”。

给定一棵 n 个节点的有根树 T，节点的编号为 1 ∼ n，根节点为 1 号节点。你需要回答 q 个询问，询问给定两个整数 p 和 k，问有多少个有序三元组 (a; b; c) 满足：

1. a、 b 和 c 为 T 中三个不同的点，且 a 为 p 号节点；

2. a 和 b 都比 c 不知道高明到哪里去了；

3. a 和 b 谈笑风生。这里谈笑风生中的常数为给定的 k。

看到这题第一反应：woc点分治裸题233。

写了一回：woc点分治怎么写？？？

所以这就是为什么用主席树的原因了（并不

前两个条件只要固定了a和b我们就知道c的方案一定是a（或b，取决于谁深度大）的子树大小-1.

事实上对于一个节点，它周围可以谈笑风生的节点要么是它的祖先要么是它子树的点。

对于前者，处理dep数组之后就很好解决了。

对于后者，dfs序更新节点再树上主席树维护dep数组记录每个节点的子树大小-1（前缀和）。

查询的时候就是正常的主席树了。

PS：1.5h debug结果：思维定式，结果把主席树建成了和以前树上主席树一样的树就gg，错误请看代码。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=3e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt;}e[N*2];struct tree{ int l,r; ll sum;}tr[N*20];int cnt,n,q,head[N],sz[N],dep[N];int rt[N],idx[N],tot,pool,maxd;inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}void insert(int y,int &x,int l,int r,int p,ll w){ tr[x=++pool]=tr[y]; tr[x].sum+=w; if(l==r)return; int mid=(l+r)>>1; if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,w); else insert(tr[y].r,tr[x].r,mid+1,r,p,w);}ll query(int y,int x,int l,int r,int l1,int r1){ if(r1
            
             
              >1; return query(tr[y].l,tr[x].l,l,mid,l1,r1)+ query(tr[y].r,tr[x].r,mid+1,r,l1,r1);}void dfs1(int u,int f,int d){ idx[u]=++tot; sz[u]=1;dep[u]=d; maxd=max(maxd,d); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==f)continue; dfs1(v,u,d+1); sz[u]+=sz[v]; }}void dfs2(int u,int f){ insert(rt[idx[u]-1],rt[idx[u]],1,maxd,dep[u],sz[u]-1); //错误点，曾经写成insert(rt[idx[f]],rt[idx[u]],1,maxd,dep[u],sz[u]-1); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==f)continue; dfs2(v,u); }}int main(){ n=read(),q=read(); for(int i=1;i
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：

+++++++++++++++++++++++++++++++++++++++++++