P3174 [HAOI2009] 毛毛虫 （树的直径变式）
题目
对于一棵 \(N\) \((N \le 3\times 10^5)\) 个点的树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫。
求点数最多的毛毛虫
题解
本题与树的直径的求法非常类似
设 \(f_u\) 表示以 \(u\) 为头的毛毛虫的最大点数
那么转移就是
\[f_u=\max_{v\in \text{son}_u}f_v+1+\max\lbrace0,\text{cnt}_u-1\rbrace \]其中 \(\text{cnt}_u\) 表示的是 \(u\) 结点的儿子的个数
然后对于每个点取最大值和次大值进行一个拼接,计算答案即可
时间复杂度\(\mathcal O(N)\)
[BZOJ 3743] Kamp （多次dfs多种信息的处理）
题目
一颗树\(n\)个点，\(n-1\)条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有\(K\)个人（分布在K个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，把这\(K\)个人分别送回去。
请你回答，对于\(i=1~n\)，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。
\(K\le N\le 5\times 10^5\)
\(1\le x,y\le N, 1\le z\le 10^6\)
题解
我们找出包含那\(k\)个关键点所组成的最小的连通块，通过画图得知
- 如果举行聚会的位置在联通块内，那么我们发现答案就是这个联通块的边权和乘\(2\)并减去联通块的直径
- 如果举行聚会的位置在连通块外，那么我们发现答案就时这个\((这个点到联通块的最短距离+连通块的边权和)\times 2-这个点到联通块中点的最远距离\)
因此考虑树形\(dp\)
记
\[\begin{aligned} &ans_i~~~在第i个点举行聚会的最短时间 \\&sum~~~关键点生成树的边权之和 \\&dis_i~~~点i到生成树的最短距离 \\&maxlen_i~~~点i与到最远关键点的距离\\&f_i~~~点i子树中关键点的个数 \\&g_i~~~点i子树外关键点的个数 \end{aligned} \]我们可以一次\(dp\)求出\(i\)的子树内关键点的个数，第二次换根\(dp\)求出\(i\)子树外关键点的个数，如果一个点子树内或子树外的关键点的个数为\(0\),那么这个点就不在关键点生成树中
通过三四次\(dp\)，我们可以求出\(dis_i\)
注意，我们如果求出了关键点生成树的直径的两个端点，设根据求直径时的过程，我们知道，对于在生成树上的点，生成树中距离它最远的点一定是其到直径两个端点的最大值
然后 \(ans_i\) 的转移如下
\[ans_i=2\times (sum+dis_i)-maxlen_i \]所以总计四次(或三次)\(dp\)便可以转移出答案
P1131 [ZJOI2007] 时态同步 （普通树形dp）
题解
\(sb\)题一道
由于时间只加不减，对于一个点\(i\),求出它子树中的最大时间和原总时间，那么答案的新贡献就是\(最大时间\times siz[i]-原总时间\)
BZOJ 4033 树上染色 （树形背包）
题目
有一棵点数为\(N\)的树，树边有边权。给你一个在\([0,N]\)之内的正整数\(K\)，你要在这棵树中选择\(K\)个点，将其染成黑色，并将其他的\(N-K\)个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
\(N\le 2000,0\le K\le N\)
题解
经典题，树形背包\(dp\)
设\(f[i][j]\)表示子树\(i\)中选了\(j\)个黑点时的全局最大距离，同时维护下子树大小\(siz[i]\)
考虑转移，我们发现，对于一个结点\(i\)，转移时的答案就是\(子树内距离+跨子树距离\)
我们对于一个子树\(v\)，枚举一个\(l\)表示子树中染了\(l\)个黑点，那么子树内的距离就是\(f[v][l]\)
那么子树外的点如何计算呢？我们不妨考虑一个经典套路，考虑每一条边的贡献
对于一条边\(e\),它被经过的次数就是两边同色点个数乘积的和，贡献就再乘上边权就可以了
所以转移就可以这么写
\[f[u][i]=\max_{v\in son(u)}\lbrace f[v][l]+cnt_{black}+cnt_{white}\rbrace \\ cnt_{black}=l\times(k-l) \\ cnt_{white}=(siz[u]-l)\times(n-k-siz[u]+l) \]感性理解是每一对点都只会在它们的 \(\text{lca}\) 处被合并一次,所以均摊后时间复杂度是 \(\mathcal O(n^2)\)
严格证明需要势能分析,不展开了
[hdu 6854] Kcats （笛卡尔树dp）
题目
定义维护单调栈的过程为：每次将栈头大于当前数的数弹栈，直到不能弹为止，然后加入当前数。
给一个长度为\(n\)的数组\(a\)，问有多少个排列\(p\)满足，将\(p\)的前\(i\)个数依次加入单调栈后，得到栈的大小为\(a_i\)。若\(a_i=−1\)表示 \(a_i\)可以等于任意值。
\(n\le 100\)
题解
我们考虑如果没有\(-1\)这道题应该怎么做
考虑笛卡尔树的构建过程，我们每次选择当前区间\([l,r]\)的最小值的位置\(p\)(对应到原题就是从左到右找到最后一个\(a[i]=1\)的位置)，我们发现最小值将整个区间分成了完全不相干的两个部分\([l,p-1], [p,r]\)
我们向左右两边填数，这就是一个组合数问题，显然有
\[ans_{[l,r]}=ans_{[l,p-1]}\times ans_{[p,r]}\times \binom{r-l}{p-l} \]然后我们考虑加上\(-1\)应该怎么做
设\(f[i][j][k]\)表示，考虑到区间\([i,j]\),当前区间初始栈的大小为\(k\),也就是当前区间笛卡尔树根的深度为\(k\)时的方案数。
那么我们枚举这个区间的笛卡尔树根\(p\),如果\(a_p\)有值则\(k\)只能取\(a_p\)，否则就将当前点改成\(k\)进行转移，转移方程如下
\[\begin{aligned} f[i][j][k]=\sum_{i\le p\le j}f[i][p][k]\times f[p+1][j][k+1]\times \binom{r-l}{p-l} \end{aligned} \]所以合着这实际是道区间\(dp\)
[CEOI2007] 树的匹配 Treasury （树上父子关系的讨论）
题目
给一棵 \(N\) 个点的树，你可以匹配有边相连的两个点，问你这棵树的最大匹配是多少，并且计算出有多少种最大匹配
\(N\le 3\times 10^5\)
题解
设 \(f[i][0/1]\) 表示 \(i\) 不与其父亲匹配/与其父亲匹配时的最大匹配; \(g[i][0/1]\) 表示不与其父亲匹配/与其父亲匹配时的最大匹配方案数
其中 \(f[i][1]\) 与 \(g[i][1]\) 是好求的,有
\[f[i][1]=\sum_{j\in \text{son}_i}f[j][0]+1\\ g[i][1]=\prod_{j\in \text{son}_i} g[j][0] \]剩下两个麻烦一些,令 \(\text{sum}=\sum_{k\in\text{son}_i} f[k][0]\) 则
\[f[i][0]=\max_{j\in \text{son}_u}\lbrace \text{sum}-f[j][0]+f[j][1]\rbrace\\ g[i][1]=\sum_{\text{满足}f[j][0/1]\text{是最大匹配}的 j}\frac{\text{sum}\times g[j][1]}{g[j][0]} \]时间复杂度 \(\mathcal O(N)\)
关于匹配的另一个小trick
最大匹配唯一其实等价于图中的一个点要么孤立，要么属于最大匹配
P4630 [APIO2018] 铁人两项 （圆方树上dp）
题解
考虑到当我们固定\(s,f\)时，我们\(c\)的选择就是\(s\)到\(f\)所有简单路径的并，然后减去\(2\)(因为\(c\)不可以选在\(s,f\)处)
进一步考虑，\(s\)到\(f\)简单路径的并就是路径上点双大小的并
所以建出原图的圆方树，将方点的权值设为这个点双中圆点的个数，将圆点的权值设为\(-1\)，那么从\(s\)到\(f\)简单路径的并就是圆方树上\(s\)到\(f\)的路径
我们设\(f_i\)表示\(s,f\)在\(i\)子树中的方案数，考虑枚举中转点\(c\)，分两种情况转移
- 点\(c\)是圆点时，假设它有\(4\)棵子树，它的子树对答案的贡献是
看上去这个转移是\(\mathcal O(n^2)\)的,是我们可以这么做
\[S_1S_2+(S_1+S_2)S_3+(S_1+S_2+S_3)S_4 \]所以我们每次记一个前缀子树和，然后乘上下一个子树的大小进行转移，这是\(\mathcal O(n)\)的
- 当\(c\)是方点，如果\(s,f\)不在这个点双内，那么其贡献一定被这个点双中的圆点中就已经统计过了，所以考虑如何计算\(s,f\)在点双内的方案数
- 如果\(s,f\)中只有一个在点双中，那么\(c\)可以选的位置就有\(deg-1\)个，总共有\(deg\times (deg-1)\)次贡献，但是当\(f\)选在了割点处，那么\(c\)就无处可选了，乘的另外一部分是相同的，所以整个就少选了\(deg\)次，所以总次数就变成了\(deg\times (deg-2)\)
- 如果\(s,f\)都在点双内部，显然可以选择的位置就有\(deg-2\)个
所以在上面圆点的转移乘上\(deg-2\)的系数就行了
HDU 5593 ZYB's Tree （换根dp）
题目
给定一个 \(n\) 个点的树,每条边的边权是 \(1\)
对于每个点,求出离这个点距离不超过 \(k\) 的点的个数
\(n \le 5\times 10^5,k\le 10\)
题解
所谓换根dp,就是先一遍 \(\text{dfs}\) 求出子树内的信息,再一次 \(\text{dfs}\) 通过求出的子树内信息去递推子树外的信息
对于这一道题,首先,一个点的答案显然可以分为子树内的点和子树外的点,于是我们设 \(f[u][d]\) 表示 \(u\) 子树内距离 \(u\) 为 \(d\) 的点的个数, \(g[u][d]\) 表示 \(u\) 的子树外距离 \(u\) 为 \(d\) 的点的个数
对于 \(f[u][d]\) ,我们可以在向上的时候转移:
\[f[u][d]=\sum_{v\in \text{son}_u}f[v][d-1] \]对于 \(g[u][d]\) ,我们可以在向下的时候转移:
\[g[u][d]=g[\text{fa}][d-1]+f[\text{fa}][d-1]-f[u][d-2] \]因为 \(u\) 点的子树外相当于 \(\text{fa}\) 点的子树外加上 \(\text{fa}\) 点的子树内除了 \(u\) 以外的儿子的答案
答案直接将同一个点的 \(f,g\) 相加去取即可,时间复杂度 \(\mathcal{O}(nk)\)
P4381 [IOI2008] Island （基环树dp+单调队列优化dp）
题目
给定一个 \(n\) 个点 \(n\) 条边的基环树森林,边有边权,求每棵基环树的直径长度之和
题解
对于这种基环树的题,先将环和树分开考虑
对于每一棵基环树上的树求出它的直径,并求出它上面的点到环的最远距离为,记它于环的那个公共点为 \(i\) ,记这个最远距离为 \(d[i]\),记环上两点 \(x,y\) 的之间的最长距离为 \(\text{dist}[x][y]\),那我们就是要在环上求出 \(\max\lbrace d[x]+d[y]+\text{dist}[x][y]\rbrace\) 我们先破环成连,然后对于这种转移区间长度固定的dp,考虑使用单调队列优化即可。然后再与各个子树的直径取最大值就是答案
HDU 3586 Information Disturbing （二分+树形dp）
题目
给定一个 \(n\) 个点树,边有边权
现在要求切除其中的一些边,使得叶节点与根节点是不连通的
要求切除的总边权不可以超过 \(m\) ,求所有的切除方案中最大边权的最小值
\(n\le 1000 m\le 10^6\)
题解
首先看到最大值最小,而且答案看上去是关于最小总花费单调的,所以我们考虑进行一个二分
二分一个值为 \(\text{mx}\) ,那么我们要求在dp的过程中不可以切除大小超过 \(\text{mx}\) 的边,设 \(f[u]\) 表示 \(u\) 与它的儿子都断开的最小花费
那么对于边 \((u,v)\) 显然有两种转移
- 断开边 \((u,v)\) 花费 \(w(u,v)\) ,即 \(f[u]\leftarrow f[u]+w(u,v)\)
- 在 \(v\) 中就把所有叶子断开了,即 \(f[u]\leftarrow f[u]+f[v]\)
大小超过 \(\text{mx}\) 的就把它特判掉就行,时间复杂度 \(\mathcal O(n\log V)\) ,其中 \(V\) 是边权的值域大小
CF 960E Alternating Tree （拆贡献经典套路）
题目
给定一棵带点权的树，求所有有向路径的权值和。
一条有向路径的权值如下定义：
设这条路径依次经过的点的权值分别为 \(V_1, V_2, ..., V_m\)。
则路径的权值为 \(\sum_{i=1}^m(-1)^{i+1}V_i\)
\(n\le 2\times 10^5\)
题解
首先,偶数长度的路径对答案是没有任何贡献的,因为这条路径的反向路径一定存在且会抵消掉这条路径的贡献
然后直接计算是困难的,所以考虑计算每个点对答案的贡献,也就是要求出每个点作为路径上的偶数位置和奇数位置多少次,
设 \(f[u][0/1]\) 表示 \(u\) 子树内的点距离 \(u\) 为偶数/奇数的点构成的路径对答案的贡献,转移是平凡的
设 \(g[u][0/1]\) 表示距离 \(u\) 为偶数/奇数的点构成的路径对答案的贡献,初始状态为 \(g[1][0/1]=f[1][0/1]\) ,转移就是 \(g[u][0/1]=g[\text{fa}][1/0]\) ,由这个转移,我们可以知道当 \(u\) 的深度是奇数时,\(g[u][0/1]=f[1][0/1]\) ,当 \(u\) 的深度是偶数时,\(g[u][0/1]=f[u][1/0]\) ,这样我们就可以求出由 \(u\) 子树外的点到 \(u\) 的长度为偶数/奇数的贡献次数,于是我们就可以采用和 "P4630 [APIO2018] 铁人两项" 相似的转移方法去计算答案即可
时间复杂度 \(\mathcal O(n)\)
POJ 2486 Apple Tree （树上路径问题1）
题目
给定一棵 \(n\) 个点的树,每个点上有一个权值，求从 \(1\) 出发，走 \(m\) 步，最多能遍历到的权值
\(n\le 100,m\le 200\)
题解
设 \(f[u][d][0/1]\) 表示没有端点/一个端点在 \(u\) 的子树内(回到 \(u\) ),走 \(d\) 步时能遍历到的最多的权值是多少
转移分三种情况转移,注意边 \((u,v)\) 被经过的次数
- 从 \(u\) 到其子树中再回到 \(u\)
- 从\(v\) 返回到 \(u\) ,再到其子树
- 直接从 \(u\) 到其子树
转移即可
P7163 [COCI2020-2021#2] Svjetlo （树上路径问题2）
题解
难以使用语言描述的题,与 "POJ 2486 Apple Tree" 不同的是这道题没有规定起点,所以本题关键思路在于设 \(f,g,h\) 分别表示路径断端点不在子树内/有一个端点在子树内/两个端点都在子树内,然后分情况讨论,具体转移方程见代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,inf=0x3f;
inline int read()
{
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
int n,rt,f[N][2],g[N][2],h[N][2];
//表示走完子树之后，u是1开还是0关
//f是两头出,g是一头出,h是两头都在子树内
string c;
int cnt,head[N];
struct Edge{
int v,nxt;
}edge[N<<1];
inline void add_edge(int u,int v)
{
edge[++cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
bool ok[N];
inline void init(int u,int fa)
{
if(c[u-1]=='1') ok[u]=1;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(v==fa) continue;
init(v,u);
ok[u]&=ok[v];
}
return;
}
inline int Min(int x,int y,int z)
{
return min(x,min(y,z));
}
inline void dfs(int u,int fa)
{
f[u][c[u-1]-'0']=0;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(v==fa||ok[v]) continue;
dfs(v,u);
int f0=f[u][0],f1=f[u][1],g0=g[u][0],g1=g[u][1],h0=h[u][0],h1=h[u][1];
//u,v均开灯 u,v均关灯
f[u][1]=min(f0+f[v][0]+2,f1+f[v][1]+4);
//u关v开 u开v关
f[u][0]=min(f1+f[v][0]+2,f0+f[v][1]+4);
//u,v均开灯 u,v均关灯
g[u][1]=min(g0+f[v][0]+2,Min(g1+f[v][1]+4,f0+g[v][1]+1,f1+g[v][0]+3));
//u开v关 u关v开
g[u][0]=min(g1+f[v][0]+2,Min(g0+f[v][1]+4,f1+g[v][1]+1,f0+g[v][0]+3));
//u,v均开灯 u,v均关灯
h[u][1]=Min(min(f0+h[v][0]+2,f1+h[v][1]+4),min(g0+g[v][0]+2,g1+g[v][1]),min(h0+f[v][0]+2,h1+f[v][1]+4));
//u关v开 u开v关
h[u][0]=Min(min(f1+h[v][0]+2,f0+h[v][1]+4),min(g1+g[v][0]+2,g0+g[v][1]),min(h1+f[v][0]+2,h0+f[v][1]+4));
}
//当x为根时
g[u][0]=min(g[u][0],f[u][1]+1);
g[u][1]=min(g[u][1],f[u][0]+1);
h[u][0]=min(h[u][0],g[u][0]);
h[u][1]=min(h[u][1],g[u][1]);
//cout<<u<<" "<<f[u][1]<<" "<<f[u][0]<<endl;
return;
}
signed main()
{
n=read();
cin>>c;
for(int i=1;i<n;++i)
{
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
for(int i=1;i<=n;++i) if(c[i-1]=='0') rt=i;
init(rt,0);
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
memset(h,0x3f,sizeof(h));
dfs(rt,0);
printf("%lld\n",h[rt][1]);
return 0;
}
ZR2023 NOIP 10连测 Day5 T2 （树上背包变式+二项式定理权值钦定）
题意
给定一个 \(n\) 个点的有根树 \(T\)，根为 \(1\)。
对于一个 \(1\sim n\) 的排列 \(a\)，设 \(k\) 表示有多少个点 \(u\) 满足它的所有祖先 \(v\) 都有 \(a_u\le a_v\) 。我们定义这个排列的权值为 \(m^k\)。
你需要求出所有排列的权值之和。答案对 \(998244353\) 取模。
题解
首先，我们发现直接去记每个点是否是到根路径上的最小点是困难的，所以我们考虑容斥原理，松弛一下条件，钦定 \(i\) 个点是合法的（我们称这些点为钦定点），那么对于一个选了 \(k\) 个点的方案，我们设 \(f_i\) 为钦定 \(i\) 个点的方案数的系数，它们满足下面的关系
\[\sum_{i=0}^k\binom{k}{i}f_i=m^k \]利用二项式定理或者GF可以解出 \(f_i=(m-1)^i\) ，即每增加一个钦定点时就要乘上 \(m-1\)
然后我们发现，如果以钦定点建立一棵虚树，虚树的lca节点之间并不是单纯的拓扑序关系，所以我们还需要把 \(u\) 给记到状态里
设 \(f[u][i]\) 表示以 \(u\) 为根的子树当中放了排列 \(1\sim \text{siz}_u\) ，钦定点编号最大为 \(i\) 时对答案的贡献
我们先考虑合并子树答案。设 \(\text{pre}[i],F[i],G[i]\) 表示钦定点的值 \(\le i\) 时的总贡献，即 \(f\) 数组的前缀和，拿 \(F,G\) 分别存下两棵子树的答案，并合并到 \(\text{pre}\) 中
先默认 \(u\) 不是钦定点并且选的值大于等于子树中的最大钦定点编号，记两棵子树的目前考虑的最大钦定点分别为 \(a,b\) （\(a\le i,b\le j\)），那么最后合并结果无非是 \(a\) 在前或者 \(b\) 在前。假设说 \(a\) 在前，那么另外一边只要不越过第 \(j\) 个位置（即 \(b\) \(\le j\) ），那么就可以转移到 \(i+j\) 位置上 （钦定点的值 \(\le i+j\) ），最后是贡献到了 \(a+j\) 上（如果不求前缀和这里会统计漏答案）。也就是对于每一个 \(a\) ，都需要和所有可能的 \(b\) 计算答案。对于 \(b\) 在前的情况也要这么做 ，转移即为
\[\text{pre}[i+j]\leftarrow F[i]\times G[j]\times \binom{i+j}{i}\times \binom{\text{siz}_u+\text{siz}_v-i-j}{\text{siz}_u-i} \]那两个组合数就是在计算前 \(i+j\) 个数和后 \(\text{siz}_u+\text{siz}_v-i-j\) 个数在两个子树中是怎么分配的（即合并两个子树排列的方案数），然后上面对最大钦定点 \(a\) 和 \(b\) 大小关系的分讨，可以直接合并为两个前缀和的乘积，即 \(F[i]\times G[j]\)
然后再把前缀和 \(\text{pre}\) 数组还原回去就能得到合并后的 \(f[u][i]\) 了
接下来考虑插入 \(u\)
- 如果 \(u\) 是非钦定点，那么它只要保证不小于子树里编号最大的那个钦定点，即 \(u\ge i\) ，这样 \(u\) 一共就有 \(\text{siz}_u-i\) 种选择，乘上去转移即可
- 如果 \(u\) 是钦定点，那么就从钦定点大小为 \(1\sim i-1\) 的位置更新过来，系数即为最开始所求的 \(m-1\)
时间复杂度 \(\mathcal O(n^2)\) ，瓶颈在于类似于树形背包的那一部分
CODE:
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=5010,mod=998244353;
int n,m,C[N][N],f[N][N],F[N],G[N],pre[N];
struct Edge{
int v,nxt;
}edge[N<<1];
int cnt,head[N];
inline void add_edge(int u,int v)
{
edge[++cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
int siz[N];
inline void dfs(int u)
{
f[u][0]=1;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].v;
dfs(v);
F[0]=f[u][0];G[0]=f[v][0];
for(int j=1;j<=siz[u];++j) F[j]=(F[j-1]+f[u][j])%mod;
for(int j=1;j<=siz[v];++j) G[j]=(G[j-1]+f[v][j])%mod;
for(int j=0;j<=siz[u]+siz[v];++j) pre[j]=0;
for(int j=0;j<=siz[u];++j)
for(int k=0;k<=siz[v];++k)
(pre[j+k]+=1ll*F[j]*G[k]%mod*C[j+k][j]%mod*C[siz[u]+siz[v]-j-k][siz[u]-j]%mod)%=mod;
for(int j=siz[u]+siz[v];j>=1;--j) (pre[j]-=pre[j-1])%=mod,(pre[j]+=mod)%=mod;
for(int j=0;j<=siz[u]+siz[v];++j) f[u][j]=pre[j];
siz[u]+=siz[v];
}
F[0]=0;
siz[u]++;
for(int i=1;i<=siz[u];++i) F[i]=(F[i-1]+f[u][i-1])%mod;
for(int i=0;i<siz[u];++i) f[u][i]=1ll*f[u][i]*(siz[u]-i)%mod;
for(int i=1;i<=siz[u];++i) (f[u][i]+=1ll*F[i]*(m-1)%mod)%=mod;
return;
}
inline void init()
{
for(int i=0;i<N;++i) C[i][0]=1;
for(int i=1;i<N;++i)
for(int j=1;j<=i;++j)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
int main()
{
init();
n=read();m=read();
for(int i=2;i<=n;++i) add_edge(read(),i);
dfs(1);
int ans=0;
for(int i=0;i<=n;++i) (ans+=f[1][i])%=mod;
printf("%d\n",ans);
return 0;
}
ZR2023 NOIP赛前20连测 Day11 T2 （增加状态维数+常规树形dp）
题意
给定一棵有根树，保证标号为一个合法的 dfs 序。把树的所有叶子按照编号顺序取出，设为 \(u_1,u_2,\dots,u_m\)。额外添加 \(m\) 条形如 \((u_i,u_{i+1})\) 的无向边（\(u_{m+1}=u_1\)）。求新图的匹配个数，对 998244353 取模。
匹配：一个边集 \(S\) 满足其所有边的所有端点两两不同。匹配个数即位合法的边集个数（重边算不同的边）
\(n\le 10^5\)
题解
如果没有叶子之间的连边，那我们直接记 \(f[u][0/1]\) 表示以 \(u\) 为根的子树， \(u\) 是否被匹配，然后直接转移就行
为了处理叶子之间连成的环，我们给 dp 加两个状态，设 \(f[u][0/1][0/1][0/1]\) 表示以 \(u\) 为根的子树，\(u\) 是否被匹配，子树内编号最小的点是否被匹配，子树内编号最大的点是否被匹配。
考虑 \(u\) 的儿子 \(v\) 如何转移到 \(u\) ，我们记两边编号最小和最大的点分别是 \(l,r\) 和 \(L,R\)，转移的时候考虑让 \(r\) 向 \(L\) 连边，如果有一边只有一个儿子，那就直接让那个儿子向另外一边连就行了
统计答案时，对于 \(u\) 的 \(l,r\) 均未被匹配的情况，可以考虑匹配 \(l\) 和 \(r\) ，也就是要算两次贡献
由于题目保证了读入顺序一定满足 \(dfs\) 序，所以直接 dfs 算就行了
时间复杂度 \(\mathcal O(n)\) ，带一个 \(32\) 的常数
code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=1e5+10,mod=998244353;
int n;
int siz[N];
int f[N][2][2][2],g[2][2][2],ok[N];
vector<int> G[N];
inline void dfs(int u)
{
if(!G[u].size())
{
f[u][0][0][0]=1;
siz[u]=1;
ok[u]=1;
return;
}
siz[u]=0;
for(int v:G[u])
{
dfs(v);
if(!siz[u])
{
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
{
(f[u][0][j][k]+=f[v][i][j][k])%=mod;
if(ok[v]&&!i) (f[u][1][1][1]+=f[v][i][j][k])%=mod;
else if(!i) (f[u][1][j][k]+=f[v][i][j][k])%=mod;
}
}
else
{
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
g[i][j][k]=0;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
for(int a=0;a<2;++a)
for(int b=0;b<2;++b)
for(int c=0;c<2;++c)
{
(g[a][b][k]+=f[u][a][b][c]*f[v][i][j][k]%mod)%=mod;
if(!i&&!a) (g[1][b][ok[v]?1:k]+=f[u][a][b][c]*f[v][i][j][k]%mod)%=mod;
if(!c&&!j) (g[a][siz[u]>1?b:1][siz[v]>1?k:1]+=f[u][a][b][c]*f[v][i][j][k]%mod)%=mod;
if(!i&&!a&&!c&&!j&&!ok[v]) (g[1][siz[u]>1?b:1][siz[v]>1?k:1]+=f[u][a][b][c]*f[v][i][j][k]%mod)%=mod;
}
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
f[u][i][j][k]=g[i][j][k];
}
siz[u]+=siz[v];
}
}
signed main(){
n=read();
for(int i=2;i<=n;++i) G[read()].emplace_back(i);
dfs(1);
int ans=0;
for(int i=0;i<2;++i)
{
for(int j=0;j<2;++j)
{
for(int k=0;k<2;++k)
{
(ans+=f[1][i][j][k])%=mod;
if(!j&&!k&&siz[1]>1) (ans+=f[1][i][j][k])%=mod;
}
}
}
cout<<ans<<'\n';
return 0;
}