CF1930G

Cute_Fish · 2026-11-13 10:07:04 · 题解

考虑 dp，设 f_{i} 表示当前 f(a) 结尾的数为 i 的方案数，初始时 f_1=1，答案即 f_n。

考虑转移 i\to j(i<j) 有什么条件：

• 对于 \operatorname{LCA}(i,j) 朝 i 方向的子树，显然 i 一定是这个子树里面的最大值。

直接做是 O(n^2) ，考虑优化，记 t_u=\max_{x\in \operatorname{path}_{1,fa_u}} x,p_u=\max_{x\in subtree_u} x。

对于祖先的贡献：若 u<t_u 则 f_u 为 0，否则，可以从 t_u 直接转移过来。

对于祖先其他子树 x 的贡献，显然只需考虑 p_x，若 p_x\in(t_u,u) 则有贡献 f_{p_x}。上一个 BIT 维护区间和，按 p_x 升序的顺序访问子树，同时动态维护贡献即可。

做到了 O(n\log n) 复杂度，可以通过。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e6 + 7;
const int mod = 998244353;
int n, f[N], mx[N], t[N], c[N];
vector<int> e[N];
inline int lowbit(int x)
{
    return x & (-x);
}
inline void update(int i, int C)
{
    for (; i <= n; i += lowbit(i))
        c[i] += C;
    return;
}
inline int query(int i)
{
    if(i<=0)return 0ll;
    int res = 0;
    for (; i; i -= lowbit(i))
        res += c[i];
    return res;
}
inline void dfs1(int u, int fa)
{
    mx[u] = u, t[u] = max(t[fa], fa);
    for (auto v : e[u])
        if (v != fa)
            dfs1(v, u), mx[u] = max(mx[u], mx[v]);
    sort(e[u].begin(), e[u].end(), [&](const int &x, const int &y)
         { return mx[x] < mx[y]; });
}
inline void dfs2(int u, int fa)
{
    if (t[u] > u)
        f[u] = 0;
    else
        f[u] = max(1ll, f[t[u]] + query(u - 1) - query(t[u] - 1)) % mod;
    for (auto v : e[u])
        if (v != fa)
            dfs2(v, u), update(mx[v], f[mx[v]]);
    for (auto v : e[u])
        if (v != fa)
            update(mx[v], -f[mx[v]]);
}
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        e[i] = {}, t[i] = f[i] = c[i] = 0;
    f[1] = 1;
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0), dfs2(1, 0);
    cout << f[n] << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
}

:::