[USACO 2019.12 Platinum]Tree Depth

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\ \begin{array}{|} \hline \color{pink}{\text{The principal is really a god}} \\ \color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\ \color{pink}{\text{holding a sharp pen to pierce the truth}} \\ \color{pink}{\text{Who can resist him? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{green}{\text{校長は本当に神であり、左側にトイレ、右側にヨンシェンがあり}} \\ \color{green}{\text{鋭いペンを持って真実を突き刺している。誰が彼に抵抗できるだろうか? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{lightblue}{\text{Le principal est vraiment un dieu}} \\ \color{lightblue}{\text{avec des toilettes à gauche et Yongshen à droite}} \\ \color{lightblue}{\text{tenant un stylo pointu pour percer la vérité}} \\ \color{lightblue}{\text{Qui peut lui résister ? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{purple}{\text{Der Direktor ist wirklich ein Gott}} \\ \color{purple}{\text{mit einer Toilette links und Yongshen rechts}} \\ \color{purple}{\text{der einen spitzen Stift hält}} \\ \color{purple}{\text{um die Wahrheit zu durchdringen.}} \\ \color{purple}{\text{Wer kann ihm widerstehen? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{cyan}{\text{Principalis deus est, Yongshen a dextris cum latrina}} \\ \color{cyan}{\text{acuto stylo ad perforandum veritatem: quis resistet ei? }} \\ \hline \end{array} \\ \color{red}{\text{对曰:“无人,狗欲当之,还请赐教!”}} \\ \newcommand\bra[1]{\left({#1}\right)} \newcommand\Bra[1]{\left\{{#1}\right\}} \newcommand\dx[0]{\text{dx}} \newcommand\string[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand\down[2]{{#1}^{\underline{#2}}} \newcommand\ddiv[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand\udiv[2]{\left\lceil\frac{#1}{#2}\right\rceil} \newcommand\lcm[0]{\operatorname{lcm}} \newcommand\set[1]{\left\{{#1}\right\}} \]


其实最后就是建出来一棵笛卡尔树,但是如果仍然计算深度,我们无法避免地要将整棵树建出来,不妨先做个转化:

\[dep_u=\sum_{v=1}^n[\text{LCA}(u,v)=v] \]

那么,我们先解决这样一个问题:

用一个排列构建笛卡尔树,一个点成为另一个点的祖先的情况是什么?

不妨考察使用单调栈建立笛卡尔树的过程,假设我们想让 \(j\) 成为 \(i\) 的祖先,针对他们的前后情况分类讨论:

  • 当 \(i>j\),则在 \(j\) 进入栈的过程中 \(i\) 已经进过栈了,此时,如果想让 \(i\) 成为 \(j\) 子树中的点,只有可能是 \(j\) 足够小,将至少从 \(i\) 开始到栈顶的所有元素都弹出了;
  • 当 \(j<i\) 时,那么 \(j\) 应该能 “存活” 到 \(i\) 进入栈中,并且不会被 \(i\) 弹出;

综合上面两个条件,我们都注意到,\(j\) 应该具备 “打赢” \([i,j]\) 中所有数字的能力,即 \(j\) 为该区间中最小的数字。

我们再解决一个问题 —— 刚好有 \(k\) 个逆序对的排列数?传送门 to 原题.


接下来,我们先固定 \(i,j\),表示区间左右端点,现在想让 \(j\) 成为 \(i\) 的祖先,先考察 \(i<j\) 的情况。

由于所有的方案都可以表示成

\[h(x)=f(x)\times g(x)=\prod_{p=1}^{n}\bra{\sum_{a=0}^{p-1}x^a} \]

其中 \(g(x)\) 为 \(j\) 点与 \([i,j]\) 区间构成的逆序对个数的生成函数,而 \(f(x)\) 就是去除前面所述的生成函数,\(f(x)\) 是未知的。但是,不难发现 \(g(x)\) 的表达式:

\[g(x)=\sum_{a=0}^{|i-j|}x^a \]

此时我们希望的是,\(j\) 和区间 \([i,j]\) 构成 \(j-i\) 个逆序对,其对应生成函数应为

\[G(x)=x^{j-i} \]

那么,该情况下的生成函数应为

\[H(x)=\frac{h(x)}{g(x)}\times G(x)=\prod_{p=1}^{n}\bra{\sum_{a=0}^{p-1}x^a}\times \frac{1}{\sum_{a=0}^{|i-j|}x^a}\times x^{|i-j|} \]

十分有意地加上绝对值,这样能够比较轻易地发现,\(j<i\) 的情况几乎和 \(i<j\) 的情况一样,唯一的区别就是,\(G(x)=1\) 而非 \(x^{|i-j|}\) 了,仅仅只有这一项不同而已......

应该注意到的是,后两项似乎都和具体的 \(i,j\) 取值无关,它仅仅至只与 \(|i-j|\) 有关,因此我们可以改为枚举区间长度 \(len\) 而非 \(i,j\) 的具体取值。而最前面的显然可以直接预处理了。

但是还有问题,就是如何处理 \(\prod_{p=1}^{n}\bra{\sum_{a=0}^{p-1}x^a}\) 这个东西,具体地,我们如何处理

\[\bra{\sum_{p=0}^{m}a_px^p}\times \bra{\sum_{q=0}^{n}x^q} \]

结果十分简单,得到的多项式就是

\[\sum_{p=0}^{n+m}\bra{\sum_{i=\max\set{0,p-m}}a_i}x^p \]

使用前缀和(或者某些更简便的方法)就可以了。

注意到当 \(i=j\) 时也存在贡献,此时贡献其实就是 \([x^k]h(x)\).

暴力做 \(\rm FFT\) 会 \(\rm T\) 掉,但是直接暴力乘上去反而还可以过......当然,如果你想做分段进行 \(\rm FFT\) 应该也可以。

预处理大概是 \(\mathcal O(N^3)\) 的,如果你使用分段 \(\rm FFT\)(并不是分治)应该可以达到 \(\mathcal O(N^2\log N)\). 计算答案复杂度是 \(\mathcal O(N^3+N^2)\),所以总复杂度就是 \(\mathcal O(N^3/N^2\log N)\).

叁、参考代码 ¶

# include <cstdio>
# include <algorithm>
# include <cstring>
# include <vector>
# include <ctime>
# include <cstdlib>
using namespace std;

// # define NDEBUG
# include <cassert>

namespace Elaina {

# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar('\n')
# define mmset(a, b) memset(a, b, sizeof (a))
# define mmcpy(a, b) memcpy(a, b, sizeof (a))

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <class T> inline T fab(T x) { return x<0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
template <class T> inline T readin(T x) {
    x=0; int f=0; char c;
    while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
    for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
    return f? -x: x;
}

template <class T> inline void writc(T x, char s='\n') {
    static int fwri_sta[55], fwri_ed=0;
    if(x<0) putchar('-'), x=-x;
    do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
    while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
    putchar(s);
}

} using namespace Elaina;

const int maxn=300;

int n, k, mod;

/** @brief poly @p f multiply another poly @p (1+x^1+x^2+...+x^{m-1}) */
inline void multi(vector<int>& f, int m) {
    assert(m>0); int n=f.size(); f.resize(n+m-1);
    for(int i=n-1-1; i>=0; --i) f[i+m]=(f[i+m]+mod-f[i])%mod;
    for(int i=1; i<n+m-1; ++i) f[i]=(f[i]+f[i-1])%mod;
}
/** @brief the reverse option of @p multi() */
inline void sub(vector<int>& f, int m) {
    assert(m>0); int n=f.size();
    for(int i=n-1; i>0; --i) f[i]=(f[i]+mod-f[i-1])%mod;
    for(int i=0; i<n-1; ++i) f[i+m]=(f[i+m]+f[i])%mod;
}

inline int get(vector<int>& f, int p) {
    if(p<0 || p>=(int)f.size()) return 0;
    return f[p];
}

signed main() {
    n=readin(1), k=readin(1), mod=readin(1);
    vector<int>h(1, 1);
    rep(i, 1, n) multi(h, i);
    vector<int>ans(n, h[k]);
    for(int len=1; len<=n; ++len) {
        sub(h, len+1);
        int latter=get(h, k-len), former=get(h, k);
        multi(h, len+1);
        for(int i=0; i<n-len; ++i) {
            ans[i+len]=(ans[i+len]+former)%mod;
            ans[i]=(ans[i]+latter)%mod;
        }
    } for(int i=0; i<n; ++i) writc(ans[i], ' '); Endl;
    return 0;
}

肆、关键 の 地方 ¶

真的没想到这道题也可以使用生成函数做......真的离谱。不过十分重要的一点是

\[dep_u=\sum_{v}[\text{LCA}(u,v)=v] \]

同样是树,它还拥有另外一个结论:

\[\sum_{u}dep_u=\sum_{u}siz_u \]

上一篇:JZ1186 【提高】背包问题00 题解


下一篇:多源最短路多种实现方式