北京网站建设 网站维护,浏览器网页视频下载,十大国际展览公司,余姚网站建设ARC142D Deterministic Placing
题目大意
有一棵nnn个顶点的树#xff0c;每个点上最多放一张卡片#xff0c;你可以做如下操作#xff1a;
同时将所有的卡片移到它所在顶点的相邻的一个顶点上
一个操作我们说它是好的#xff0c;当下列条件满足#xff1a;
每条边最…ARC142D Deterministic Placing
题目大意
有一棵nnn个顶点的树每个点上最多放一张卡片你可以做如下操作
同时将所有的卡片移到它所在顶点的相邻的一个顶点上
一个操作我们说它是好的当下列条件满足
每条边最多被某张卡片经过每个顶点最多被一张卡片占据
小TTT可以选择一个或多个顶点来放置卡片一个顶点放置一张卡片。他有2n−12^n-12n−1种方式求满足以下条件的方案数 对于每个非负整数kkk
它能连续进行kkk次好的操作令SkS_kSk表示经过刚好kkk次操作后被卡片占据的点的集合则SkS_kSk是唯一的 题解
第一步分树为链
我们可以发现每一张卡片都是在两个点上反复横跳的。我们把每个反复横跳的边拿出来那一定是若干条不相交的链。且这些链一定是以空点为顶部有卡片的点为中部和尾部一条链不能只有一个空点。这些链一定能填满整棵树。
假设x,yx,yx,y为相邻的两个点且在不同的链上为了避免重复和不合法的情况我们做一些规定。
如果xxx链的端点且yyy为链的中间点则在第二次操作时在yyy上的卡片可以向xxx移动则SkS_kSk不唯一如果x,yx,yx,y都是链的顶部则第一次操作后两条链合并成一条链可以往两个方向移动SkS_kSk不唯一如果x,yx,yx,y都是链的尾部则第一次操作时xxx的位置空出了yyy所在可以往链头或xxx移动SkS_kSk不唯一
其余情况都是合法的。 第二步树形DP
定义fu,if_{u,i}fu,i表示点uuu第iii种状态下的方案数。各种状态如下
fu,0f_{u,0}fu,0表示uuu为链身且uuu在链上无前无后fu,1f_{u,1}fu,1表示uuu为链身且uuu在链上有前无后fu,2f_{u,2}fu,2表示uuu为链身且uuu在链上无前有后fu,3f_{u,3}fu,3表示uuu为链身且uuu在链上有前有后fu,4f_{u,4}fu,4表示uuu为链头且uuu在链上无后面的点fu,5f_{u,5}fu,5表示uuu为链头且uuu在链上有后面的点fu,6f_{u,6}fu,6表示uuu为链尾且uuu在链上无后面的点fu,7f_{u,7}fu,7表示uuu为链尾且uuu在链上有后面的点
有前或有前面的点即存在链头有后或有后面的点即存在链尾。
为了防止在转移的时候计算重复我们还需要定义gu,ig_{u,i}gu,i。假设当前枚举的是uuu的各个儿子且枚举到的儿子为vvv则fu,if_{u,i}fu,i表示点uuu在统计vvv之前的各种状态的方案数ggg表示统计vvv之后的方案数则可以用fu,if_{u,i}fu,i和fv,if_{v,i}fv,i来更新ggg在vvv的贡献计算完之后再将ggg的值赋值给fff然后计算uuu的下一个儿子。
因为状态比较多所以转移式也比较多。除去不合法的情况有202020种转移方法具体见代码。
对于每个点状态0,4,60,4,60,4,6的fff的初值为111。最后的答案为f1,3f1,5f1,7f_{1,3}f_{1,5}f_{1,7}f1,3f1,5f1,7。 总结
这道题主要是用树形DP考虑各种状态来进行状态转移。时间复杂度为O(n)O(n)O(n)。
注代码中gt(v1,v2,v3)gt(v1,v2,v3)gt(v1,v2,v3)表示gu,v1fu,v2×fv,v3g_{u,v1}f_{u,v2}\times f_{v,v3}gu,v1fu,v2×fv,v3vvv为uuu的儿子。这一步即用uuu点的状态v2v2v2的fff和vvv点的状态v2v2v2的fff值更新ggg的状态v1v1v1。
code
#includebits/stdc.h
using namespace std;
int n,x,y,tot0,d[500005],l[500005],r[500005];
long long v[10],f[200005][8];
long long mod998244353;
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void pt(int v1,int v2,int v3){v[v1](v[v1]f[x][v2]*f[y][v3]%mod)%mod;
}
void dfs(int u,int fa){f[u][0]f[u][4]f[u][6]1;for (int ir[u];i;il[i]){if(d[i]fa) continue;dfs(d[i],u);for (int j0;j8;j) v[j]0;xu;yd[i];pt(0,0,3);pt(1,0,4);pt(1,0,1);pt(1,1,3);pt(2,0,6);pt(2,0,2);pt(2,2,3);pt(3,2,4);pt(3,1,6);pt(3,1,2);pt(3,2,1);pt(3,3,3);pt(4,4,7);pt(5,5,7);pt(5,4,2);pt(5,4,6);pt(6,6,5);pt(7,7,5);pt(7,6,1);pt(7,6,4);for(int j0;j8;j) f[u][j]v[j];}
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d%d,x,y);add(x,y);add(y,x);}dfs(1,0);printf(%lld,(f[1][3]f[1][5]f[1][7])%mod);return 0;
}
