CF755G PolandBall and Many Other Balls

经典生成函数题目。

设计状态 $f_{i,j}$ 表示从前 $i$ 个球中选出 $j$ 组，容易得到状态转移方程 $f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-2,j-1}$。尝试写成生成函数的形式，设 $F_i(x)$为 $f_{i,j}$ 生成函数，有：

$$F_i(x)=(x+1)F_{i-1}(x)+xF_{i-2}(x)$$

大概有以下几种做法。

矩阵快速幂

注意到这是一个比较简单的递推的形式，转移显然可以用矩阵刻画。与普通矩阵快速幂唯一的不同是，现在矩阵中的元素是一个多项式。直接矩阵快速幂即可。时间复杂度为 $\mathcal O(k\log k\log n)$。

倍增

通项公式

组合意义

考虑暴力计算 $f(k)$ 的一个式子：$\displaystyle f(k)=\sum_{i=1}^k \binom{k}{i}\binom{n-i}{k}$。

关于 $n$ 的项不好处理。然后就是很巧妙的了（不知道从那种角度入手能够想到）。我们重新单独考虑 $\displaystyle \binom{k}{i}\binom{n-i}{k}$ 的组合意义，相当于选中有一排小球，先从前 $k$ 个中选 $i$ 个，再在剩下的中选 $k$ 个。注意两次选的球不能重复，利用此条件进行容斥。设 $g(i)$ 表示恰好有 $i$ 个球重复， $h(i)$ 表示钦定有 $i$ 个球重复。$g(i),h(i)$ 显然存在如下关系：

$$h(j)=\sum_{i=j}^k \binom{i}{j} g(i)$$

考虑 $h(i)$ 的值，容易得到：

$$h(i)=\binom{k}{i}\binom{n-i}{k-i}2^{k-i}$$

具体意义是，先从前 $k$ 个中钦定 $i$ 个重复的，另外的 $k-i$ 个随便选。再从后面的 $n-i$ 个选出剩下的 $k-i$ 个。接下来使用二项式反演得出 $g(i)$ 的表达式：

$$\begin{align} g(j)&=\sum_{i=j}^k (-1)^{i-j} \binom{i}{j} h(i)\notag\\ &=\sum_{i=j}^k (-1)^{i-j} \binom{i}{j} \binom{k}{i}\binom{n-i}{k-i}2^{k-i}\notag \end{align}$$

尝试求出答案 $f(k)$，并进行化简：

$$\begin{align} f(k)&=g(0)\notag\\ &=\sum_{i=0}^k (-1)^i \binom{k}{i}\binom{n-i}{k-i}2^{k-i}\notag\\ \end{align}$$

这其实是我们想要的形式！将组合拆开，注意到关于 $n$ 的项显然变得好处理了一些。进一步得到：

$$\begin{align} f(k)&=\sum_{i=0}^k (-1)^i \binom{k}{i}\binom{n-i}{k-i}2^{k-i}\notag\\ &=\sum_{i=0}^k (-1)^i \frac{k!}{i!(k-i)!}\frac{(n-i)!}{(k-i)!(n-k)!}2^{k-i}\notag\\ &=\sum_{i=0}^k (-1)^i \frac{k!}{i!(k-i)!}\frac{(n-i)!}{(k-i)!(n-k)!}2^{k-i}\notag\\ &=\frac{k!}{(n-k)!}\sum_{i=0}^k \frac{(-1)^i(n-i)!}{i!}\frac{2^{k-i}}{((k-i)!)^2}\notag\\ \end{align}$$

但是关于 $n$ 的阶乘项还是不好处理，尝试化成下降幂的形式：

$$\begin{align} f(k)&=\frac{k!n!}{(n-k)!}\sum_{i=0}^k \frac{(-1)^i(n-i)!}{i!n!}\frac{2^{k-i}}{((k-i)!)^2}\notag\\ &=k!n^{\underline k}\sum_{i=0}^k \frac{(-1)^i}{i!n^{\underline i}}\frac{2^{k-i}}{((k-i)!)^2}\notag\\ \end{align}$$

于是直接卷积即可得到答案。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int T,n,k;
int tot,head[N],ver[N<<1],e[N<<1],ne[N<<1];

struct Heap
{
    priority_queue<ll,vector<ll>,greater<ll> >h1,h2;
    ll v,tag1,tag2;
    Heap() : v(-1),tag1(0),tag2(0){}
    int size(){return h1.size()+h2.size()+(v!=-1);}
    void add(ll val)
    {
        if(h1.size()<k/2)return h1.push(val-tag1);
        if(val>h1.top()+tag1)
        {
            ll ne=h1.top()+tag1;
            return h1.pop(),h1.push(val-tag1),add(ne);
        }
        if((k&1)&&v==-1)return v=val,void();
        if((k&1)&&val>v)
        {
            ll ne=v;
            return v=val,add(ne);
        }
        if(h2.size()<k/2)return h2.push(val-tag2);
        if(val>h2.top()+tag2)h2.pop(),h2.push(val-tag2);
    }
}f[N];

inline void add(int u,int v,int w)
{
    ver[++tot]=v;
    e[tot]=w;
    ne[tot]=head[u];
    head[u]=tot;
}
inline void init()
{
    tot=0;
    memset(head,0,sizeof(head));
}
inline void merge(Heap &x,Heap &y)
{
    if(x.size()<y.size())swap(x,y);
    while(!y.h1.empty())x.add(y.h1.top()+y.tag1),y.h1.pop();
    while(!y.h2.empty())x.add(y.h2.top()+y.tag2),y.h2.pop();
    if(~y.v)x.add(y.v),y.v=-1;
}
void dfs(int x,int fa)
{
    f[x].add(0);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        f[y].tag1+=e[i]<<1,f[y].tag2-=e[i]<<1;
        merge(f[x],f[y]);
    }
}
inline void solve()
{
    init();
    read(n);
    k=n;
    ll ans=0;
    for(int i=1,u,v,w;i<n;i++)
    {
        read(u,v,w);
        add(u,v,w),add(v,u,w);
    }
    dfs(1,0);
    
    while(!f[1].h1.empty())ans+=f[1].h1.top(),f[1].h1.pop();
    while(!f[1].h2.empty())ans+=f[1].h2.top(),f[1].h2.pop();
    if((k&1)&&(~f[1].v))ans+=f[1].v,f[1].v=-1;
    printf("%lld\n",-ans);
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    read(T);
    // T=1;
    while(T--)solve();
    return 0;
}