P6773题解

0 前言

给机房新同学一场欢迎赛的I题。其实就是防AK题。

因为讲评还要讲这道题，所以这两天赶紧学习了一下。

非常经典的一道题目，难度真的非常大。但这才是真正的绝世好题。

鲜花：想起来我第一次见到这个题目是在2022年，我来机房的第一年。我当时还非常不聪明，看一位学长讲这个题，当时傻乎乎的觉得太难了可能永远学不会。三年多后的今天轮到我给机房的同学们讲这道题了，这也真的是命运吧。

拜读了题解区第一、二篇题解，写得非常清晰透彻，在此感谢。

1 题意

原题题目描述真的又臭又长。

给定一棵 $n$ 个点的树，现在可以选择对这棵树的每条边进行染色或者不染色。有 $m$ 条限制，第 $i$ 个限制形如 $(u_i,v_i)$，意为要求树上从 $u_i$ 到 $v_i$ 的路径上至少有一条边被染色，保证 $u_i$ 是 $v_i$ 的祖先。求满足全部 $m$ 个限制的方案数，答案对 $998244353$ 取模。

2 思路

16pts

这个很简单吧。

32pts

简单容斥。

对于题目中所描述的结构计数，我们一时间想不到从正面DP的方法。于是正难则反，我们考虑不满足题目条件的方案数，再用 $2^{n-1}$ 减去就是答案。

直接推导的话，我们发现不满足题目条件就是从限制里面分别选出大小为 $1\sim m$ 的子集，对于子集计数就可以了。

我们假设对于第 $i$ 条限制而言，能够满足的方案集合为 $S_i$，则所有不满足的方案数也就是 $|\cup^m_{i=1}\overline{S_i}|$ 。对这个东西做容斥原理，显然有

$$|\cup^m_{u=1}{\overline{S_u}}|=\sum^m_{i=1}{(-1)^{i-1}\sum_{a_j<a_{j+1}}{|\cap_{k=1}^{i}{\overline{S_{a_i}}}|}}$$

发现：${|\cap_{k=1}^{i}{\overline{S_{a_i}}}|}=2^{n-1-sum}$，其中 $sum$ 是所选限制对应链的并长度。

上面的东西如果使用二项式反演也是一样的道理，只不过推导更加直接简洁。

怎么处理 $sum$ 呢？可以每次算得时候给这些链染色然后查询染上色的链数量，树剖一下就可以做了。

于是不需要思考的，时间复杂度 $O(m2^mlog^2n)$ 的做法横空出世，可以获得 $32pts$ 的好成绩。

64pts

这是最有意义的一档部分分了。

很显然，接着上面的容斥思路想下去就是死路一条。按理说这时候肯定是往DP的方向去想了，但是怎么DP呢？

考虑要在状态中维护哪些信息，根据我们在树上DP题目的一般经验，我们要从叶子往上合并子树，同时考虑到题目的限制，我们还要对处于不同位置的限制作考虑。也就是我们要在状态中维护当前节点和节点子树中的限制。

发现对于一个节点 $x$ ，所有限制分为三种（下文称第一，二，三类限制）：

• $(u,v)$ 全都在 $x$ 子树内，这种限制是一定要满足的；
• $(u,v)$ 全都不在 $x$ 子树内，这种限制目前没法处理，也暂时不需要去管它；
• $(u,v)$ 中 $v$ 在 $x$ 子树内而 $u$ 不在，这种限制是我们讨论的重点，因为我们既可以算在 $x$ 子树内就满足这个限制的方案数，也可以算暂时不满足这个限制，等到向上转移再说的方案数。

我们先想第一个问题：怎么在状态里维护子树内限制的信息？

如果严格按照空间来算，用 $f_{x,0/1}$ 表示第一类限制全都满足，第三类限制有/没有全都满足。但是这显然是没法转移的。因为虽然 $f_{x,1}$ 向上转移勉勉强强还好，但是 $f_{x,0}$ 向上转移时根本没法知道具体哪些限制没有全都满足。

那么问题来了：我们怎么把未满足的第三类限制的信息压缩到一个数字之内？

这需要一个很关键的观察：我们发现，对于一群未满足的第三类限制，把它分成两部分：

• 在 $x$ 子树内的部分，由于这些限制目前都未满足，所以这一部分应该都是没有染色的。
• 在 $x$ 子树外的部分。发现这一部分是重叠起来的一条链，所以此时满足限制产生了依赖：满足了短的段就一定满足长的段。

我们最终要满足所有限制，所以这里的关键在于未满足的第三类限制中 $x$ 往上的链的最大深度，也就是所有未满足第三类限制 $(u,v)$ 的 $dep_{u_{max}}$。

我们此时的状态就这样设计好了：设 $f_{x,i}$ 表示在 $x$ 的子树中，第一类限制都已满足，第三类限制未满足的最大深度为 $i$ 。

接下来考虑转移。

还是从底向上合并子树信息，我们当前的节点是 $x$，即将进行合并到的子节点是 $y$。记对于限制 $(u_1,v),(u_2,v),\ldots$，$anc_v=u_{max}$，其中 $u_{max}$ 表示前面的限制里面表示深度最大的 $u$。我们接下来可以讨论一下这条边的染色问题：

• 给 $(x,y)$ 染色。那么很显然，$y$ 子树中所有的限制全都会满足，对 $x$ 子树中的信息没有影响。 因此贡献是 $f_{x,i}\times \sum_{j=dep_{anc_y}}^{dep_y} f_{y,j}$
• 不给 $(x,y)$ 染色。发现此时 $y$ 会给 $x$ 子树中的信息造成影响，所以我们分几种情况讨论：
  • $f_{y,j}$，其中 $j<i$。这时候 $y$ 子树内的限制对于 $x$ 无影响，所以贡献很简单是 $f_{x,i}\times \sum_{j=1}^{i-1} f_{y,j}$
  • $f_{y,j}$，其中 $j=i$。这个时候发现我们的 $f_{x,i}$ 不仅仅可以由原来的 $f_{x,i}$ 转移过来了，因为 $f_{y,i}$ 帮我们限定好了最深深度，所以这部分的贡献是 $f_{y,i}\times \sum^{i}_{j=1}{f_{x,j}}$。
  • $f_{y,j}$，其中 $j>i$。不难发现这种情况的贡献不可能被加到 $f_{x,i}$ 中，因为我们不能让 $y$ 子树中的更深的限制来更新当前我们钦定 $x$ 子树的最深限制。

至此，我们的DP转移方程新鲜出炉：

$$f_{x,i}=f_{x,i}\times \sum_{j=dep_{anc_y}}^{dep_y}{f_{y,j}}+f_{x,i}\times \sum_{j=1}^{i-1} f_{y,j}+f_{y,i}\times \sum^{i}_{j=1}{f_{x,j}}$$

至于边界条件的话，考虑限制 $f_{x,dep_{anc_x}}$，这个状态代表着把 $x$ 子树里面第一、三类限制都满足了。这种情况有 $f_{x,dep_{anc_x}}=1$。为什么呢？因为你最开始还没合并的时候相当于什么限制都没有，可行的方案数量当然是 $1$。

有人就要问了：这个东西看上去是 $O(n^2m)$ 的啊，$64pts$是怎么拿到的？

不难发现中间有很多区间和的问题，考虑可以用前缀和来优化一下。同时，发现一个状态 $f_{x,i}$ 有效信息的区间仅在 $[dep_{anc_x},dep_x]$ 之内，其他位置都为 $0$，所以其实只需要维护前缀就可以了。

设 $g_{x,i}=\sum_{j=0}^{i}{f_{x,j}}$，则DP式子就变成：

$$f_{x,i}=f_{x,i}\times g_{y,dep_y}+f_{x,i}\times g_{y,i-1}+f_{y,i}\times g_{x,i}$$

朴素地进行DP的话，复杂度是 $O(nm)$，理论上仅可以获得 $48pts$，卡卡常甚至这样也可以 $64pts$。

这时候还有人要问了：上面的分析中出现了 $anc_x$ 和 $anc_y$，我们把所有限制的两端端点统称为“关键点”，那么遍历到了不是关键点的 $x,y$怎么办呢？

实际上答案是没有影响。我们让非关键点的点 $anc_w=0$，正常跑DP就可以了。

但是这给了我们启发：关键点的数量有限，我们的DP并不是在每一个深度上都有用。

于是我们可以对DP状态的第二维离散化，，可以做到 $O(n \min(n,m))$，可以稳定获得 $64pts$。

如果有更加强大的大手子想到可以只对关键点跑DP的话，建一棵虚树上面跑DP，时间复杂度优化到 $O(\min(n,m)^2)$，可以通过 $72pts$ 的数据。但是这个我没写过。

100pts

正解做法其实我觉得不如上面一档的暴力做法思维含金量高，但是是一个非常经典的trick。

这里用到了一种叫做“整体DP”的东西，就是模糊了DP每一步的具体转移，而用数据结构等等方式让整体一起转移。

首先我们简单介绍一下什么是线段树有交合并（其实这里我很同意ylx的话，应当把有交、无交合并/分裂区分开来）：两颗线段树，我们要把对应位置的值进行一些操作，比如我们合并的操作定义为数值加法，也就是把第一颗线段树上的节点的值全都加到第二棵上去。这里如果两棵树对应位置都有或者都没有节点就好办，单单一个有节点而另一个没有就需要分析。

我们先把上文推出来的式子变一变形：

$$f_{x,i}=f_{x,i}( g_{y,dep_y}+g_{y,i-1})+f_{y,i}\times g_{x,i}$$

不难发现一次转移相当于给一个位置乘上一个数再加上一个数。

我们考虑把DP数组搬到线段树上，$rt_u$ 表示 $f_{u,i}$ 所对应线段树的根，为了使空间复杂度是正确的，也是为了实现合并，必须使用动态开点。

为方便叙述，下文“线段树 $rt_u$”等于“以 $rt_u$ 为根的线段树”

我们考虑怎么用线段树合并来实现DP的过程。

首先，我们发现转移这里相当于先给 $x$ 乘上了一个数，然后把 $f_{y,i}$，也就是另一颗线段树对应位置上的一些信息合并到了这上面。因此我们想一想，让 $u$ 是这里的 $rt_x$ 这颗线段树目前遍历到的节点，$v$ 是 $rt_y$ 上的对应节点。怎么实现合并这个过程：

• 当 $u$ 和 $v$ 都不存在时，什么也干不了；
• 当 $u$ 存在而 $v$ 不存在时， 很显然我们算不了 $f_{y,i}\times g_{x,i}$，于是我们先算前面的一部分。
• 当 $v$ 存在而 $u$ 不存在时，这个时候我们可以干什么呢？可以先修改一下线段树 $rt_y$ 上 $i$ 位置的值。为什么这样是对的呢？因为这个修改后的节点将会成为我们线段树 $rt_u$ 中的新节点，等会 pushup() 一下显然就对了。
• 当 $u$ 和 $v$ 都存在时，显然把上面的式子套进来一下就好了。

问题来了：这个时候怎么维护 $g$ 呢？

其实我们发现 $g$ 因为只是维护前缀的和，所以其实没必要为其再开一个数组。在合并的时候维护两个变量，在对应节点合并答案的时候记得处理一下就可以。

所以到这里不难发现，我们线段树维护的东西其实很基础：区间和和区间乘。

在写的时候好好想一想自己究竟要实现什么东西，为了实现这个东西需要维护什么东西，为了维护这些东西需要怎么去写。捋清楚这一点写起来就并不复杂了。

3 实现

代码其实一般长度，并不是很复杂。

需要注意的两点是：

• 有很多需要取模的地方不能漏取模。
• 数组开的尽可能大。

下面是丑陋的代码：

#define elif else if
const int mod = 998244353;
const int N = 1145140;
int seg[N<<4],tag[N<<4],lb[N<<4],rb[N<<4],tot,rt[N];
int newnode(){
    tot++;
    seg[tot]=lb[tot]=rb[tot]=0;
    tag[tot]=1;
    return tot;
}
void pushup(int u){
    seg[u]=(seg[lb[u]]+seg[rb[u]])%mod;
}
void change(int u,int k){
    seg[u]=(seg[u]*k)%mod;
    tag[u]=(tag[u]*k)%mod;
}
void pushdown(int u){
    if(tag[u]!=1){
        change(lb[u],tag[u]);
        change(rb[u],tag[u]);
        tag[u]=1;
    }
}
int query(int u,int l,int r,int L,int R){
    if(!u)return 0;
    if(L<=l&&r<=R){
        return seg[u]%mod;
    }elif(r<L||R<l)return 0;
    int mid=l+r>>1;
    pushdown(u);
    return (query(lb[u],l,mid,L,R)+query(rb[u],mid+1,r,L,R))%mod;
}
void update(int u,int l,int r,int pos,int k){
    if(l==r){seg[u]=k;return;}
    int mid=l+r>>1;
    if(pos<=mid)lb[u]=newnode(),update(lb[u],l,mid,pos,k);
    else rb[u]=newnode(),update(rb[u],mid+1,r,pos,k);
    pushup(u);
}
int merge(int u,int v,int l,int r,int &preu,int &prev){
    if(!u&&!v)return 0;
    if(!u){
        prev=(prev+seg[v])%mod;
        change(v,preu);
        return v;
    }
    if(!v){
        preu=(preu+seg[u])%mod;
        change(u,prev);
        return u;
    }
    if(l==r){
        preu=(preu+seg[u])%mod;
        seg[u]=(seg[u]*prev%mod+seg[v]*preu%mod)%mod;
        prev=(prev+seg[v])%mod;
        return u;
    }
    int mid=l+r>>1;
    pushdown(u);pushdown(v);
    lb[u]=merge(lb[u],lb[v],l,mid,preu,prev);
    rb[u]=merge(rb[u],rb[v],mid+1,r,preu,prev);
    pushup(u);
    return u;
}

#define pii std::pair<int,int>
int n,m;
std::vector<int> g[N];
std::vector<int> anc[N];
pii q[N];
int dep[N];
void dfs0(int u,int fa){
    dep[u]=dep[fa]+1;
    for(auto &i:g[u]){
        if(i==fa)continue;
        dfs0(i,u);
    }
}
void solve(int u,int fa){
    rt[u]=newnode();
    int mad=0;
    for(auto &i:anc[u]){
        mad=std::max(mad,dep[i]);
    }
    update(rt[u],0,n,mad,1);
    for(auto &i:g[u]){
        if(i==fa)continue;
        solve(i,u);
        int preu=0,prev = query(rt[i],0,n,0,dep[i]-1);
        rt[u]=merge(rt[u],rt[i],0,n,preu,prev);
    }
}
signed main(){
    n=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);   
    }
    m=read();
    for(int i=1;i<=m;++i){
        q[i]={read(),read()};
        anc[q[i].second].push_back(q[i].first);
    }
    dfs0(1,0);
    solve(1,0);
    printf("%lld",query(rt[1],0,n,0,0));
    return 0;
}

4 复杂度分析

先说空间复杂度：

不难注意到只有 insert() 这个函数创建了新的节点，由于线段树层高 $O(\log n)$，所以 solve() 每遍历到一个新的点都会创建 $O(\log n)$ 个节点。总的空间复杂度 $O(n\log n)$。

再说时间复杂度：

不难发现：每个节点只可能被合并一次，也就是被父亲节点合并一次。所以总的时间复杂度也就是均摊 $O(n\log n)$ 的。

5 后记

2026要是有什么新年愿望的话，

希望OI水平能在这一年有更多的长进。

许愿：去WC2027。