P14721 题解

· · 题解

我怎么做了一个世纪。

歪解

:::info[点击观看抽搐思考过程] 首先菜菜的作者想到了只要让没有水豚的所有点互不相邻就是正确的！然后就是一个没有上司的舞会！

然后发现样例二可以摆在 \{0,3\} 上面。咦。

开始思考一个水豚的贡献是什么，发现可以让一只水豚管辖两个点，然后一直穿过中间的边，这样就可以覆盖完整。然后变成一个边覆盖！只要让所有不被覆盖的边全部都不相邻就是正确的。但是发现有重合顶点的不是很好做。直接放在点上不就能做吗。

然后发现一只水豚其实可以刻画成管辖一个或者两个点，于是这个东西就好维护了。最开始设计成一个点的子树里面有多少个颜色以及当前节点要不要和父亲匹配。然后样例二又爆炸了！为什么呢，因为不同的分割方式最后得到的摆放集合是一样的，比如 \{\{0,1\},\{2\},\{3\}\} 和 \{\{0\},\{1,2\},\{3\}\} 都可以摆在 \{0,2,3\}，但是显然这两种划分在我们的 dp 里面算作两种。

怎么办呢，我们可以考虑把当前节点的放置状态也记录进去，于是就能做了。后面是正解。

正解

用 dp_u[k][t] 表示当前处理 u 的子树，子树内恰 k 只水豚，且子树内除了 u 全都处理好了，按 u 的状态分四类：

t 含义
a_0 u 有水豚，u 可以向上匹配或者自己独立
a_1 u 有水豚，u 被占用
b u 是空点，被占用
c u 是空点，必须和父亲匹配

对的你说为啥独立放在 a_0 这么变态，因为这个相当于按这个点所处块的大小分类，比较好刻画。

合并儿子的时候记录以下内容：

Z=\prod_v(a_0{+}a_1{+}b),\quad Y=\prod_v(a_1{+}b),\quad E=\sum_v c_v\prod_{w\ne v}(a_0{+}a_1{+}b)_w

其中：

转移（u 自己是水豚则 k 偏移 +1）：

a_0[k]=Z[k-1],\quad a_1[k]=E[k-1],\quad b[k]=Z[k]-Y[k],\quad c[k]=Y[k]

根节点不能有父亲，所以 \text{ans}[k] = a_0[k]+a_1[k]+b[k]（c 肯定是被弃掉的）。

复杂度的分析大概是每个无序点对只在 LCA 处被合并一次，O(n^2)。

Code

// Author: albertting
// Time: 2026/11/12 12:18:00

#include <bits/stdc++.h>
using namespace std;

using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

constexpr i32 MOD = 998244353;
void addto(i32 &x, i32 y) {
    x += y;
    if(x >= MOD) x -= MOD;
}
vector<i32> conv(const vector<i32> &a, const vector<i32> &b) {
    vector<i32> res(a.size() + b.size() - 1, 0);
    for(size_t i = 0; i < a.size(); i++) {
        if(a[i] == 0) continue;
        for(size_t j = 0; j < b.size(); j++) {
            res[i + j] = (res[i + j] + (i64)a[i] * b[j]) % MOD;
        }
    }
    return res;
}

vector<i32> solve(i32 N, vector<i32> U, vector<i32> V) {
    vector<vector<i32> > adj(N);
    for(i32 i = 0; i < N - 1; i++) adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]);
    vector<i32> par(N, -1), ord;
    ord.reserve(N);
    vector<i32> st = {0};
    par[0] = 0;
    while(!st.empty()) {
        i32 u = st.back();
        st.pop_back();
        ord.push_back(u);
        for(i32 w : adj[u]) {
            if(w == par[u]) continue;
            par[w] = u;
            st.push_back(w);
        }
    }
    vector<vector<array<i32, 4> > > dp(N);
    for(auto it = ord.rbegin(); it != ord.rend(); it++) {
        i32 u = *it;
        vector<i32> Z(1, 1), Y(1, 1), E(1, 0);
        for(i32 v : adj[u]) {
            if(v == par[u]) continue;
            auto &g = dp[v];
            i32 m = (i32)g.size();
            vector<i32> p(m), q(m), r(m);
            for(i32 k = 0; k < m; k++) {
                i32 a0 = g[k][0], a1 = g[k][1], b = g[k][2], c = g[k][3];
                p[k] = ((a0 + a1) % MOD + b) % MOD, q[k] = (a1 + b) % MOD, r[k] = c;
            }
            vector<i32> Zn = conv(Z, p), En = conv(E, p), Zr = conv(Z, r);
            size_t L = max(En.size(), Zr.size());
            En.resize(L, 0), Zr.resize(L, 0);
            for(size_t k = 0; k < L; k++) addto(En[k], Zr[k]);
            Z = move(Zn), E = move(En), Y = conv(Y, q);
            vector<array<i32, 4> >().swap(dp[v]);
        }
        i32 m = (i32)Z.size();
        vector<array<i32, 4>> h(m + 1);
        for(i32 k = 0; k <= m; k++) {
            i32 a0 = k >= 1 ? Z[k - 1] : 0, a1 = k >= 1 ? E[k - 1] : 0, b = 0, c = 0;
            if(k < m) {
                b = Z[k] - Y[k];
                if(b < 0) b += MOD;
                c = Y[k];
            }
            h[k] = {a0, a1, b, c};
        }
        dp[u] = move(h);
    }
    vector<i32> ans(N + 1, 0);
    auto &g = dp[0];
    for(i32 k = 0; k <= N; k++) if(k < (i32)g.size()) ans[k] = ((g[k][0] + g[k][1]) % MOD + g[k][2]) % MOD;
    return ans;
}

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(0), cout.tie(0), cerr.tie(0);

//     i32 N; cin >> N;
//     vector<i32> U(max(N - 1, 0)), V(max(N - 1, 0));
//     for(i32 i = 0; i < N - 1; i++) cin >> U[i] >> V[i];
//     vector<i32> ans = solve(N, U, V);
//     for(i32 k = 0; k <= N; k++) cout << ans[k] << (k == N ? '\n' : ' ');
//     return 0;
// }