百度 2026 初赛第一轮题解

主观难度评分：

Easy：01, 05, 07

Medium：02, 04

Medium Hard：03，06

Hard：08

01

首先发现，药一定越靠后用越优，然后就是你在 ab 都能杀的情况下，先杀 a 和先杀 b 没区别，所以我们让血少的在前面一定不劣，所以把 $(a_i,b_i)$ 存进数组，按 $a_i$ 从小到大排序，打不动了再用药水即可。然后要注意一下最后药水可能会有剩余，全用掉即可。

CPP

void solve() {
    int n, k, s; in >> n >> k >> s;
    std::vector<pii> a(n+1);
    rep(i,1,n) in >> a[i].fi >> a[i].se;
    sort(a.begin()+1,a.end(),[&](pii x,pii y) { return x.fi < y.fi; });
    rep(i,1,n) {
        if(a[i].fi <= s) { s += a[i].se; }
        else {
            while(a[i].fi > s && k) s *= 2, k--;
            if(a[i].fi <= s) s += a[i].se;
        }
    }
    while(k) s *= 2, k--;
    out << s << '\n';
}

05

用 $100$ 减去 $x$ 和 $y$ 即可。

CPP

void solve() {
    int x, y; in >> x >> y;
    out << 100 - x - y << '\n';
}

07

先讨论一下没有 $-1$ 的情况，此时只有得票最多的人会当选，注意只能有一个，如果有多个人得票同时为最多的。那么没有人可能当选。

由于一共只有 $n$ 票，所以未知的票数是固定的，是 $n - sum$ ，我们枚举每个人，判断能不能让他成为最高票的即可。

具体的，若 $a_i = -1$ ，我们把全部的未知票都给他，判断 $n - sum$ 是否大于原序列的最大值。若 $a_i \ne -1$ ，因为 $a_i \ne -1$ 的位置的票数已经确定，所以我们把票在 $a_i = -1$ 的所有位置均摊，此时均摊开的最值是 $\lceil \frac{n-sum}{\sum[a_i=-1]} \rceil$ ，判断当前位置是不是唯一的原序列最值，还有能不能比在 $a_i = -1$ 的位置均摊开的最值大即可。

注意要特判一下除以 $0$ 。

CPP

void solve() {
    int n; in >> n;
    vi a(n+1);
    rep(i,1,n) in >> a[i];
    int mx = 0;
    rep(i,1,n) ckmax(mx,a[i]);
    int mxc = 0;
    rep(i,1,n) if(a[i] == mx) mxc++;
    int s = 0;
    int cnt = n;
    rep(i,1,n) if(a[i] != -1) s += a[i], cnt--; 
    int c = n - s;

    rep(i,1,n) {
        if(a[i] == -1) {
            if(c > mx) out << i << ' ';
        } else {
            if(cnt == 0) {
                if(a[i] >= mx && mxc == 1) out << i << ' ';
                continue;
            }
            if((c + (cnt-1)) / cnt < a[i] && a[i] >= mx && mxc == 1) {
                out << i << ' ';
            }
        }
    }
}

02

首先考虑最终变成答案的那个长度为 $k$ 的区间。

设这 $k$ 个元素在原数组中的位置一共分成 $c$ 段连续区间，那么需要的最少翻转次数正好是 $c-1$ 。

所以 $c$ 段可以用 $c-1$ 次操作合并。

一次区间翻转只有两个端点会改变“选中 / 未选中”的相邻关系，因此一次最多让选中位置的连续段数减少 $1$ ，所以至少也要 $c-1$ 次。

因此原问题等价为：选择 $k$ 个元素，使它们在原数组的位置至多组成 $m+1$ 个连续段，最小化这些元素的极差。

接着考虑固定一个值域 $[L,R]$ 。

把满足

L\le a_i\le R

的位置全部标记出来，它们在原数组上会形成若干个连续段，长度为

s_1,s_2,\ldots,s_c.

我们最多能从 $m+1$ 个连续段中选元素，所以显然应该选最长的 $m+1$ 段。

因此当前值域可行，当且仅当：最大的 $m+1$ 个连续段长度之和 $\ge k$ 。

注意并不要求恰好把这些段全部选完。如果总长度超过 $k$ ，最后一个段只取一部分即可，仍然不会增加连续段数量。

于是把所有 $(a_i,i)$ 按 $a_i$ 排序，双指针维护当前值域，相同的值一起加入、一起删除。

类似 ODT 的，我们用 map 维护当前所有连续段：

加入一个位置时，只可能和左右两个连续段合并；
删除一个位置时，只可能把所在连续段拆成左右两段。

类似对顶堆的，我们再用两个 multiset 维护所有段长：

左堆保存最大的 $m+1$ 个段长；
右堆保存剩余段长；
sum 维护左堆内段长之和。

那么当前值域是否合法只需要判断 sum >= k。

每个位置只会加入、删除一次，每次修改复杂度为 $O(\log n)$ 。

使用线段树也可以维护所有段长，具体的就是我们开一个权值线段树，记录每个段长的连续段有多少个。

再维护 $sum_i$ 表示 $cnt_i \times i$ ，查询用线段树二分找第 $m+1$ 大所在位置即可，下面提供这种做法的代码。

CPP

struct Tag {
    int add = 0;
    void apply(const Tag& t) { add += t.add; }
};

struct Info {
    int cnt = 0, sum = 0, v = 0;
    void apply(const Tag& t) { cnt += t.add; sum += v * t.add; }
    friend Info operator+(const Info& a, const Info& b) {
        return {a.cnt + b.cnt, a.sum + b.sum, 0};
    }
};

void solve() {
    int n, m, k; in >> n >> m >> k;
    std::vector<pii> a(n);
    rep(i,0,n-1) { in >> a[i].fi; a[i].se = i + 1; }
    sort(all(a));
    vi val;
    std::vector<vi> pos;
    for(int i = 0, j; i < n; i = j) {
        for(j = i; j < n && a[j].fi == a[i].fi; ++j);
        val.pb(a[i].fi);
        pos.pb({});
        rep(t,i,j-1) pos.back().pb(a[t].se);
    }
    std::vector<Info> ini(n + 1);
    rep(i,1,n) ini[i].v = i;

    SGT<Info,Tag> sgt(ini);
    std::map<int,int> seg;
    auto addl = [&](int x) { sgt.upd(x, x, {1}); };
    auto dell = [&](int x) { sgt.upd(x, x, {-1}); };

    auto add = [&](int x) {
        auto r = seg.upper_bound(x), l = r;
        bool L = 0;
        bool R = (r != seg.end() && r->fi == x + 1);
        if(r != seg.begin()) {
            --l; L = (l->se == x - 1);
        }
        if(L && R) {
            int p = l->fi, q = r->se;
            dell(l->se - l->fi + 1);
            dell(r->se - r->fi + 1);
            seg.erase(r);
            l->se = q;
            addl(q - p + 1);
        } else if (L) {
            dell(l->se - l->fi + 1);
            l->se = x;
            addl(l->se - l->fi + 1);
        } else if (R) {
            int q = r->se;
            dell(r->se - r->fi + 1);
            seg.erase(r);
            seg[x] = q;
            addl(q - x + 1);
        } else {
            seg[x] = x;
            addl(1);
        }
    };

    auto del = [&](int x) {
        auto it = prev(seg.upper_bound(x));
        int l = it->fi, r = it->se;
        dell(r - l + 1);
        seg.erase(it);
        if(l < x) { seg[l] = x - 1; addl(x - l); }
        if(x < r) { seg[x + 1] = r; addl(r - x); }
    };

    int ans = 4e18, r = 0;

    rep(l,0,(int)val.size()-1) {
        while(r < val.size() && sgt.topk(m + 1) < k) {
            for (int x : pos[r]) add(x);
            r++;
        }
        if(sgt.topk(m + 1) >= k) ckmin(ans, val[r - 1] - val[l]);
        for(int x : pos[l]) del(x);
    }

    out << ans << '\n';
}

04

首先观察边权的含义。

对于一个 $A_{l,r}$ ，可以把它看成区间 $[l,r]$ 的权值。对于一条边 $(i,j)$ ，其中 $i<j$ ，题目中的两部分分别表示：

$i\in[l,r]$ ，但 $j\notin[l,r]$ ；
$j\in[l,r]$ ，但 $i\notin[l,r]$ 。

所以 $e_{i,j}$ 实际上就是所有恰好包含 $i,j$ 中一个点的区间 $[l,r]$ 的权值和。

接下来证明一定存在一个最优匹配没有交叉，这个通过打表是易证的，可以跳过。

考虑两条相交的边

(i,k),(j,l),\qquad i<j<k<l

对于任意一个区间 $[x,y]$ ，因为它在数轴上连续，所以考虑 $i,j,k,l$ 是否属于这个区间时，属于区间的点一定也是连续的一段。

于是对这个区间单独考虑，可以发现

[\text{区间恰好包含 }i,k\text{ 之一}] + [\text{区间恰好包含 }j,l\text{ 之一}]

一定不小于

[\text{区间恰好包含 }i,j\text{ 之一}] + [\text{区间恰好包含 }k,l\text{ 之一}]

又因为所有 $A_{x,y}\ge 0$ ，所以有

e_{i,j}+e_{k,l}\le e_{i,k}+e_{j,l}

也就是说，如果匹配中存在两条交叉边 $(i,k),(j,l)$ ，我们可以把它们改成

(i,j),(k,l)

而不会让答案变大。

不断消除交叉后，一定存在一组最优匹配，其中所有边都不相交。

$\mathrm{Q.E.D.}$

于是就可以做区间 DP。

令 $f_{l,r}$ 表示区间 $[l,r]$ 内所有点进行不交叉完美匹配的最小权值，只考虑长度为偶数的区间。

假设 $l$ 和 $k$ 匹配。由于匹配不能交叉，那么剩余点一定分别在

[l+1,k-1]

和

[k+1,r]

内部独立匹配。

同时 $[l+1,k-1]$ 的长度必须为偶数，所以 $k$ 每次增加 $2$ 。

转移就是

f_{l,r} = \min_{\substack{l<k\le r\\k-l\text{ 为奇数}}} \left( f_{l+1,k-1} + f_{k+1,r} + e_{l,k} \right)

边权 $e_{i,j}$ 可以先对 $A$ 做二维前缀和。根据题目定义，

e_{i,j} = \sum_{l=1}^{i}\sum_{r=i}^{j-1}A_{l,r} + \sum_{l=i+1}^{j}\sum_{r=j}^{n}A_{l,r},

两块都是矩形，二维前缀和可以 $O(1)$ 求出，因此预处理所有边权复杂度为 $O(n^2)$ 。

最后的复杂度看起来是 $O(n^3)$ ，但由于只枚举偶数长度，并且转移时 $k$ 每次增加 $2$ ，实际转移次数会少很多。

实测转移次数大概在 $1.4 \times 10^8$ 次左右，是可过的。

CPP

const int N = 2e3+10;
int a[N][N], s[N][N], n, e[N][N], f[N][N];

void init() {
    rep(i,1,n) {
        rep(j,1,n) {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }
}

int qry(int x, int y, int xx, int yy) {
    return s[xx][yy] + s[x-1][y-1] - s[x-1][yy] - s[xx][y-1];
}

void solve() {
    in >> n;
    rep(i,1,n) rep(j,i,n) in >> a[i][j];
    init();
    rep(i,1,n) rep(j,i+1,n) {
        e[i][j] = e[j][i] =
            qry(1,i,i,j-1) + qry(i+1,j,j,n);
    }
    for(int len = 2;len <= n;len += 2) {
        rep(l,1,n-len+1) {
            int r = l + len - 1;
            f[l][r] = inf;
            for(int k = l + 1;k <= r;k += 2) {
                f[l][r] = std::min(f[l][r],f[l+1][k-1] + f[k+1][r] + e[l][k]);
            }
        }
    }
    out << f[1][n] << '\n';
}

03

首先考虑枚举 $T_1$ 上一条链的两个端点。

固定一个端点 $r$ ，枚举另一个端点 $x$ ，集合就是 $T_1$ 上的链 $P(r,x)$ 。

因为 $T_2[P(r,x)]$ 一定是一片森林，根据点减边容斥，它连通当且仅当

|V|-|E|=1.

于是定义

f_r(x)=|P(r,x)|-|E(T_2[P(r,x)])|.

这个值就是 $T_2[P(r,x)]$ 的连通块个数，所以始终有 $f_r(x)\ge1$ ，并且链合法当且仅当 $f_r(x)=1$ 。

先把 $T_1$ 以当前点 $r$ 为根。

对于一个点 $u$ ，它出现在链 $P(r,x)$ 上，当且仅当 $x$ 在 $u$ 的子树中。

所以每个点 $u$ 会对其子树内所有点贡献 $+1$ ，也就是

\operatorname{subtree}(u)\mathrel{+}=1.

再考虑 $T_2$ 中一条边 $(u,v)$ 。

它会被算进 $E(T_2[P(r,x)])$ ，当且仅当 $u,v$ 都在链 $P(r,x)$ 上。

这要求 $u,v$ 在当前根下存在祖先关系。假设 $u$ 是 $v$ 的祖先，那么只要 $x\in\operatorname{subtree}(v)$ ，链 $P(r,x)$ 就会同时经过 $u,v$ 。

因此这条边相当于

\operatorname{subtree}(v)\mathrel{-}=1.

所以固定根以后，所有 $f_r(x)$ 都可以通过若干次子树加得到。

而子树在 DFS 序上是连续区间，因此可以用线段树维护。

线段树维护：

mn：区间最小值；
cnt：最小值出现次数；
tag：区间加。

因为 $f_r(x)\ge1$ ，并且 $f_r(r)=1$ ，所以全局最小值一定为 $1$ 。于是线段树根节点的 cnt 就是当前以 $r$ 为一个端点的合法链数量。

考虑换根，先只看点的贡献。

对于 $x\in\operatorname{subtree}(v)$ ，链 $P(v,x)$ 比 $P(u,x)$ 少了一个点 $u$ ，所以值减 $1$ 。

对于 $x\notin\operatorname{subtree}(v)$ ，链 $P(v,x)$ 比原来多了一个点 $v$ ，所以值加 $1$ 。

因此可以统一写成

[1,n]\mathrel{+}=1,\qquad \operatorname{subtree}(v)\mathrel{-}=2.

考虑 $T_2$ 中一条边 $(a,b)$ 。

设 $p$ 是 $T_1$ 上从 $a$ 往 $b$ 走的第一个点，$q$ 是从 $b$ 往 $a$ 走的第一个点。

随着根在 $T_1$ 上移动，$a,b$ 是否存在祖先关系，只会在根跨过

(a,p),\qquad (b,q)

这两条边时发生变化。

因此每条 $T_2$ 边只需要挂 $O(1)$ 个换根事件。

跨过对应边时，对另一端所在的那一侧整体加上 $+1$ 或 $-1$ 。

而删掉 $T_1$ 中一条边后的一侧，要么是一个子树，要么是一个子树的补集，所以都可以用 DFS 序上的 $O(1)$ 个区间表示。

于是 DFS 换根时只需要：

TEXT

u -> v

全局 +1
subtree(v) -2
执行挂在边 (u,v) 上的所有事件

统计当前线段树 cnt

DFS(v)

撤销修改

每条 $T_2$ 边只会产生常数个事件，所以总修改次数为 $O(n)$ 。

设所有根下线段树得到的 cnt 之和为 $C$ 。

单点集合 $\{u\}$ 只会计算一次，一共有 $n$ 个，其余路径都会被计算两次。

因此最终答案为

n+\frac{C-n}{2} = \frac{C+n}{2}.

CPP

struct Tag {
    int add = 0;
    void apply(const Tag &t) { add += t.add; }
};
struct Info {
    int mn = 0, cnt = 0;
    void apply(const Tag &t) { mn += t.add; }
    friend Info operator+(const Info &a, const Info &b) {
        if (a.mn < b.mn) return a;
        if (b.mn < a.mn) return b;
        return {a.mn, a.cnt + b.cnt};
    }
};

const int N = 1e6 + 10;

int n, tim, sum;
int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rk[N], dif[N];
vi E[N];
std::vector<pii> ev[N];

SGT<Info,Tag> *tr;

void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    for(int v : E[u]) if(v != f) {
        dfs1(v, u);
        siz[u] += siz[v];
        if(!son[u] || siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++tim;
    rk[tim] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int v : E[u]) {
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

bool anc(int u, int v) {
    return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u];
}

int child(int u, int v) {
    while(top[u] != top[v]) {
        if(fa[top[v]] == u) return top[v];
        v = fa[top[v]];
    }
    return rk[dfn[u] + 1];
}

pii side(int u, int v) {
    if(!anc(u, v)) return {u, u};
    int c = child(u, v);
    return {c, -c};
}

void add_sub(int u, int w) { tr->upd(dfn[u], dfn[u] + siz[u] - 1, {w}); }

void add_side(int x, int w) {
    if(x > 0) add_sub(x, w);
    else { tr->upd(1, n, {w}); add_sub(-x, -w); }
}

void mvrt(int v, int op) {
    tr->upd(1, n, {op});
    add_sub(v, -2 * op);
    for(auto [x, w] : ev[v]) add_side(x, w * op);
}

void dfs3(int u) {
    sum += tr->info[1].cnt;
    for(int v : E[u]) if(fa[v] == u) { mvrt(v, 1); dfs3(v); mvrt(v, -1); }
}

void init() {
    rep(i,1,n) { E[i].clear(); ev[i].clear(); son[i] = dif[i] = 0; }
}

void solve() {
    in >> n;
    init();
    dif[n + 1] = 0;
    tim = 0;
    rep(i,2,n) {
        int u, v; in >> u >> v;
        E[u].eb(v); E[v].eb(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    rep(i,2,n) {
        int a, b;  in >> a >> b;
        if(anc(a, b)) {
            dif[dfn[b]]--;
            dif[dfn[b] + siz[b]]++;
        } else if (anc(b, a)) {
            dif[dfn[a]]--;
            dif[dfn[a] + siz[a]]++;
        }
        auto [ca, A] = side(a, b);
        auto [cb, B] = side(b, a);
        ev[ca].eb(B, A > 0 ? -1 : 1);
        ev[cb].eb(A, B > 0 ? -1 : 1);
    }
    rep(i,1,n) dif[i] += dif[i - 1];
    std::vector<Info> init(n + 1);
    rep(i,1,n) init[i] = {dep[rk[i]] + dif[i], 1};
    SGT<Info,Tag> tmp(init); tr = &tmp;
    sum = 0;
    dfs3(1);
    out << (sum + n) / 2 << '\n';
}

06

这是若干个互不影响的公平组合游戏，所以考虑求每台游戏机的 SG 值，最后做 nim-sum。

但这题和普通 SG 有一点不同：操作 2、3 中的 $x$ 可以任意大，因此一个状态可能有无限多个后继。比如某个状态能一步走到 SG 值 $0,1,2,3,\ldots$ ，那么它的 mex 就不是一个有限整数了，而是 $\omega$ 。

这里 $\omega$ 表示第一个无限序数。之后还有 $\omega+1,\omega+2,\ldots,\omega\cdot2,\omega\cdot2+1,\ldots$ 。

好在本题所有 SG 值都只会形如 $\omega p+q$ ，其中 $p,q$ 都是有限非负整数，所以直接用二元组 $(p,q)$ 表示即可。

对于这种形式，nim-sum 满足

(\omega p+q)\oplus(\omega x+y) = \omega(p\oplus x)+(q\oplus y)

所以最终只需要分别异或 $p,q$ 。

我们考虑求单机的 SG 值，记 $g(a,b,c)$ 表示状态 $(a,b,c)$ 的 SG 值。

先看 $c=0$ 。此时只能执行操作 1，也就是把 $a$ 变成任意更小的非负整数，所以就是普通 nim，有 $g(a,b,0)=a$ ，也就是 $g(a,b,0)=(0,a)$ 。

接下来考虑 $c>0$ 。

操作 2、3 之后都会变成 $a=b=x$ 的状态，所以先观察这些状态。可以归纳得到 $g(x,x,2k+1)=\omega(k+1)$ ，以及 $g(x,x,2k)=\omega k+(x+1)\ (k\ge1)$ 。

当 $c=1$ 时，操作 2 可以令 $c$ 变为 $0$ ，同时选择任意 $x\ge b$ 。而 $g(x,x,0)=x$ ，所以操作 2 可以到达 $b,b+1,b+2,\ldots$ 。

再考虑操作 1。如果 $a<b$ ，前面的状态依次填掉 $0,1,\ldots,a-1$ ，所以 $g(a,b,1)=a$ 。

如果 $a=b$ ，所有有限非负整数都已经成为后继，因此 $g(b,b,1)=\omega$ 。之后继续增大 $a$ ，依次得到 $\omega+1,\omega+2,\ldots$ 。

所以

g(a,b,1)= \begin{cases} a,&a<b,\\ \omega+(a-b),&a\ge b \end{cases}

当 $c=2k$ ，其中 $k\ge1$ 时，利用前面的归纳结论，操作 3 可以到达 $c\le2k-2$ 的所有对角状态，这些 SG 值能够覆盖 $[0,\omega k)$ 。

操作 2 还可以令新的 $c=2k-1$ ，而 $g(x,x,2k-1)=\omega k$ ，所以后继已经覆盖 $[0,\omega k]$ 。

因此当前 mex 从 $\omega k+1$ 开始。再通过操作 1，随着 $a$ 增大依次往后得到，所以

g(a,b,2k)=\omega k+(a+1)

注意这里与 $b$ 无关。

当 $c=2k+1$ 时，先考虑 $k\ge1$ 。

操作 3 可以覆盖 $[0,\omega k]$ ，而操作 2 取新的 $c=2k$ 时，有 $g(x,x,2k)=\omega k+(x+1)$ 。又要求 $x\ge b$ ，所以可以覆盖 $\omega k+(b+1),\omega k+(b+2),\ldots$ 。

因此这一层唯一缺少的是 $\omega k+1,\omega k+2,\ldots,\omega k+b$ 。

操作 1 会随着 $a$ 增大依次填掉这些空缺。所以当 $a<b$ 时，有 $g(a,b,2k+1)=\omega k+(a+1)$ 。

当 $a=b$ 时，这一层所有值都被覆盖，于是 mex 跳到 $\omega(k+1)$ 。之后继续随 $a$ 增大，因此

g(a,b,2k+1)= \begin{cases} \omega k+(a+1),&a<b,\\ \omega(k+1)+(a-b),&a\ge b \end{cases}

把 SG 值 $\omega p+q$ 记为二元组 $(p,q)$ ，那么最终有

g(a,b,c)= \begin{cases} (0,a),&c=0,\\[4pt] \left(\frac c2,a+1\right),&c>0,\ c\text{ 为偶数},\\[6pt] \left(\frac{c-1}{2},a+1\right),&c>1,\ c\text{ 为奇数且 }a<b,\\[6pt] (0,a),&c=1,\ a<b,\\[4pt] \left(\frac{c+1}{2},a-b\right),&c\text{ 为奇数且 }a\ge b \end{cases}

最后根据 SG 定理，把所有游戏机的 SG 做 nim-sum。

由于：

(\omega p+q)\oplus(\omega x+y) = \omega(p\oplus x)+(q\oplus y)

所以分别维护两个异或和即可。

如果最后两个异或和都为 $0$ ，则先手必败，否则先手必胜。

CPP

void solve() {
    int n; in >> n;
    int x = 0, y = 0;
    rep(i,1,n) {
        int a, b, c;
        in >> a >> b >> c;
        pii g;
        if(c == 0) {
            g = {0, a};
        } else if(c % 2 == 0) {
            g = {c / 2, a + 1};
        } else if(a >= b) {
            g = {(c + 1) / 2, a - b};
        } else if(c == 1) {
            g = {0, a};
        } else {
            g = {c / 2, a + 1};
        }
        x ^= g.fi;
        y ^= g.se;
    }
    out << (x || y ? "First" : "Second") << '\n';
}

08

设一棵以 $1$ 为根的树中，点 $i$ 的儿子数为 $s_i$ ，树的权值为

\prod_i w_{s_i}

要求点集 $\{1,2,\ldots,k\}$ 的诱导子图连通。

有结论：对于一棵 $m$ 个点、以 $r$ 为根的有标号树，令 $s_i$ 为点 $i$ 的儿子数，则

\sum_T \prod_i x_i^{s_i} = x_r\left(\sum_i x_i\right)^{m-2}

原因是 Prufer 序列中，点 $i$ 出现次数为 $\deg_i-1$ 。

对于非根节点有 $\deg_i=s_i+1$ ，所以出现 $s_i$ 次；对于根节点有 $\deg_r=s_r$ ，所以只出现 $s_r-1$ 次，因此需要额外乘一个 $x_r$ 。

记

A=x_1+x_2+\cdots+x_k,\qquad B=x_1+x_2+\cdots+x_n

因为前 $k$ 个点的诱导子图连通，而整张图是一棵树，所以前 $k$ 个点内部本身恰好是一棵树。

先只看前 $k$ 个点，它们以 $1$ 为根，贡献为

x_1A^{k-2}

接着把这 $k$ 个点整体缩成一个超级点。

缩点后有 $n-k+1$ 个点，并以超级点为根。若某个点接到超级点上，那么在原树中，它可以选择前 $k$ 个点中的任意一个作为父亲，因此超级点对应的变量不是一个单独的 $x$ ，而是 $A$ 。

所以缩点后的贡献为

A B^{n-k-1}

于是当 $k<n$ 时，所有好树的儿子数生成多项式就是

x_1A^{k-1}B^{n-k-1}

当 $k=n$ 时没有缩点后的部分，生成多项式为

x_1A^{n-2}

定义 EGF

W(x)=\sum_{i=0}^{n-1}\frac{w_i}{i!}x^i

考虑 $(x_1+\cdots+x_m)^d$ 。

若每个变量次数分别为 $c_1,\ldots,c_m$ ，那么对应系数为

\frac{d!}{c_1!c_2!\cdots c_m!}

因此把 $x_i^{c_i}$ 的权值替换成 $w_{c_i}$ 后，总和就是

d![x^d]W(x)^m

根节点 $1$ 比较特殊，因为前面额外有一个 $x_1$ 。

如果它在剩余多项式中的次数为 $c$ ，那么实际儿子数为 $c+1$ ，因此根节点对应

W'(x) = \sum_{c\ge0}\frac{w_{c+1}}{c!}x^c

先考虑 $k<n$ 。

令

q=n-k-1

因为 $B=A+C$ ，其中 $C=x_{k+1}+\cdots+x_n$ ，所以

x_1A^{k-1}B^q = \sum_{j=0}^{q} \binom qj x_1A^{k-1+j}C^{q-j}

定义

F(x)=W(x)^k,\qquad G(x)=W(x)^{n-k}

对于固定的 $j$ ，前 $k$ 个点贡献为

(k-1+j)! [x^{k-1+j}] W'(x)W(x)^{k-1}

而

W'(x)W(x)^{k-1} = \frac{1}{k}F'(x)

所以这一部分等于

\frac{(k+j)!}{k}F_{k+j}

其中 $F_i=[x^i]F(x)$ 。

后 $n-k$ 个点贡献为

(q-j)!G_{q-j}

再乘上 $\binom qj$ ，得到

\text{Ans} = \frac{q!}{k} \sum_{j=0}^{q} \frac{(k+j)!}{j!} F_{k+j}G_{q-j}

当 $k=n$ 时，

\text{Ans} = \frac{(n-1)!}{n} [x^{n-1}]W(x)^n

所以只需要求出 $W^k$ 和 $W^{n-k}$ 的前 $n$ 项，这个用 $O(nlogn)$ 的多项式幂截断即可。

CPP

void solve() {
    int n, k; in >> n >> k;
    std::vector<Z> a(n);
    rep(i,0,n-1) {
        int w; in >> w;
        a[i] = Z(w) * ifac[i];
    }
    poly W(a);
    poly F = W.pow(k, n);
    Z ans = 0;
    if(k == n) {
        ans = fac[n - 1] / Z(n) * F[n - 1];
    } else {
        poly G = W.pow(n - k, n);
        int q = n - k - 1;
        rep(j,0,q) {
            ans += fac[k + j] * ifac[j] * F[k + j] * G[q - j];
        }
        ans *= fac[q] / Z(k);
    }
    out << ans.v << '\n';
}