LibreOJ 3340. 「NOI2020」命运

考虑 DP，设 $f_{u, i}$ 表示确定了以 $u$ 为根的子树内的所有边的状态，对于所有 $v_{j}$ 在该子树内且没有被满足的 $j$ ， ${d e p}_{u_{j}}$ 的最大值为 $i$ 的方案数。特别地， $i = 0$ 表示全都满足的方案数。
之所以记最大值是因为实际上只关心最大值，深的满足了之后浅的会同时满足。

对于 $u$ 及其儿子 $v$ ，不难合并其状态

f_{u, i}^{'} = \sum_{j = 0}^{{d e p}_{u}} f_{u, i} f_{v, j} + \sum_{j = 0}^{i} f_{u, i} f_{v, j} + \sum_{j = 0}^{i - 1} f_{u, j} f_{v, i}

第一项表示把 $u$ 到 $v$ 的边标记为重要的，后两项表示标记为不重要的。

不难发现这个 DP 适合用线段树合并来维护。
直接上即可。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 5e5;
const int mod = 998244353;
int n,m;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
    struct node
    {
        int sum,tag;
        int ls,rs;
    } seg[N * 50 + 5];
    inline void push(int p)
    {
        if(seg[p].tag ^ 1)
        {
            if(seg[p].ls)
                seg[seg[p].ls].sum = (long long)seg[seg[p].ls].sum * seg[p].tag % mod,
                seg[seg[p].ls].tag = (long long)seg[seg[p].ls].tag * seg[p].tag % mod;
            if(seg[p].rs)
                seg[seg[p].rs].sum = (long long)seg[seg[p].rs].sum * seg[p].tag % mod,
                seg[seg[p].rs].tag = (long long)seg[seg[p].rs].tag * seg[p].tag % mod;
            seg[p].tag = 1;
        }
    }
    void insert(int x,int &p,int tl,int tr)
    {
        static int tot = 0;
        !p && (p = ++tot,seg[p].tag = 1);
        if(tl == tr)
        {
            seg[p].sum = 1;
            return ;
        }
        push(p);
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
        seg[p].sum = (seg[seg[p].ls].sum + seg[seg[p].rs].sum) % mod;
    }
    int query(int r,int p,int tl,int tr)
    {
        if(!p || tr <= r)
            return seg[p].sum;
        push(p);
        int mid = tl + tr >> 1;
        int ret = 0;
        ret = (ret + query(r,seg[p].ls,tl,mid)) % mod;
        r > mid && (ret = (ret + query(r,seg[p].rs,mid + 1,tr)) % mod);
        return ret;
    }
    int merge(int p,int q,int ptag,int qtag,int tl,int tr)
    {
        if(!p && !q)
            return 0;
        if(!p)
        {
            seg[q].sum = (long long)seg[q].sum * qtag % mod,
            seg[q].tag = (long long)seg[q].tag * qtag % mod;
            return q;
        }
        if(!q)
        {
            seg[p].sum = (long long)seg[p].sum * ptag % mod,
            seg[p].tag = (long long)seg[p].tag * ptag % mod;
            return p;
        }
        if(tl == tr)
        {
            ptag = (ptag + seg[q].sum) % mod,
            seg[p].sum = ((long long)seg[p].sum * ptag + (long long)seg[q].sum * qtag) % mod;
            return p;
        }
        push(p),push(q);
        int mid = tl + tr >> 1;
        int plsum = seg[seg[p].ls].sum;
        int qlsum = seg[seg[q].ls].sum;
        seg[p].ls = merge(seg[p].ls,seg[q].ls,ptag,qtag,tl,mid);
        seg[p].rs = merge(seg[p].rs,seg[q].rs,(ptag + qlsum) % mod,(qtag + plsum) % mod,mid + 1,tr);
        seg[p].sum = (seg[seg[p].ls].sum + seg[seg[p].rs].sum) % mod;
        return p;
    }
}
vector<int> top[N + 5];
int fa[N + 5],dep[N + 5];
int rt[N + 5];
void dfs(int p)
{
    int mx = 0;
    for(int u : top[p])
        mx = max(mx,dep[u]);
    SEG::insert(mx,rt[p],0,n);
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs(to[i]),rt[p] = SEG::merge(rt[p],rt[to[i]],SEG::query(dep[p],rt[to[i]],0,n),0,0,n);
}
int main()
{
    freopen("destiny.in","r",stdin),freopen("destiny.out","w",stdout);
    scanf("%d",&n);
    int u,v;
    for(register int i = 2;i <= n;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    scanf("%d",&m);
    for(;m;--m)
        scanf("%d%d",&u,&v),top[v].push_back(u);
    dep[1] = 1,dfs(1);
    printf("%d\n",SEG::query(0,rt[1],0,n));
}

『My guiding star.』

LibreOJ 3340 「NOI2020」命运