一道不错的分治ntt题目

 

题目稍微转化一下，就是所有k条链的存在交，并且交的部分都被覆盖k次

所以一定是两个点，之间路径选择k次，然后端点两开花

 

f[x]表示x子树内往下延伸k条链（可以停在x）的方案数（有标号）

每个子树选择一个或者不选择，最多一共选择k个，dp是O(n^2)的，

考虑生成函数，其实就是：

而

 

统计答案？

直接两两点对f相乘肯定不行，因为f仅仅是子树

考虑枚举x作为lca统计

如果是拐弯的链，树形DP即可。

而如果是直上直下的链，

对于不同子树，x的选择是扣去这个子树，还可以往上选择

分治NTT的经典问题

const int N=1e5+5;int n,k;int jie[N],inv[N];int A(int n,int m){    if(n<0||m<0||n
     
      >1;    divi(l,mid,lf,lg);    divi(mid+1,r,rf,rg);    f=lf*rf;    g=(lf*rg)+(lg*rf);}int f[N],sum[N],son[N];int ans,sz[N];struct node{    int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}void dfs(int x,int fa){    // cout<<" xx "<
      
       <<" fa "<
       
        <
        
         =0;--i) inv[i]=mul(inv[i+1],i+1);    int x,y;    for(reg i=1;i