首页 > 其他分享 >ARC101E Ribbons on Tree

ARC101E Ribbons on Tree

时间:2024-01-26 17:01:30浏览次数:28  
标签:sz 连通 int 配对 sum Tree times ARC101E Ribbons

思路

直接正着考虑合法的方案数不是很好做,那么正难则反,可以用总方案数减去不合法方案数,这样容斥一下就能得到答案了。

设 \(F(S)\) 表示集合 \(S\) 中的边不被覆盖的方案数。那么最后的答案就是 \(\displaystyle\sum_{S \subseteq E} (-1)^{|S|}F(S)\)。再思考 \(F(S)\) 怎么求。不难发现一些边不被覆盖相当于把整棵树分成了若干个连通块,根据 \(F\) 的定义,只要求了 \(S\) 中的边不被覆盖,其他边状态随意,因此每个连通块中都可以没有限制的配对。对于一个大小为 \(m\) 的连通块,记 \(sum_m\) 表示它的方案数,若 \(m\) 是奇数,那么任意配对的方案数就是 \(0\),否则对于第 \(1\) 个点,有 \(m-1\) 个点能与其配对,第 \(2\) 个点就要除去 \(1\) 号点配对的两个点,就有 \(m-3\) 个点能与其配对。这样类推下去,\(sum_m\) 便为 \((m-1)\times (m-3)\times\cdots \times 3 \times 1\)。那么 \(F(S)\) 就是每个连通块的方案数乘起来。

快速求解这个 \(F\),于是设 \(f_{u,i}\) 表示以 \(u\) 为根的子树内,\(u\) 所在的连通块大小为 \(i\) 对答案的贡献(不算 \(u\) 的连通块的贡献,带上容斥系数)。转移枚举 \(u\) 的儿子 \(v\) 和他们的连通块大小,分两种:

  • \(f_{u,i+j} \gets f_{u,i}\times f_{v,j}\) 表示不把 \(u,v\) 分成两个连通块,而是合并起来。
  • \(f_{u,i} \gets f_{u,i} \times f_{v,j} \times (-sum_j)\) 表示把 \(u,v\) 分成两个连通块,这时不被覆盖的边就会增加一条,容斥系数 \(\times (-1)\),同时会让当前的 \(F(S)\) 乘上新增的连通块的方案数 \(sum_j\),故转移时要 \(\times (-sum_j)\)。

最后的答案便是 \(\sum\limits_{i=1}^{n}f_{1,i}\times sum_i\),把自己所在的连通块的贡献乘上(因为状态的定义是不算自己的)。

关于时间复杂度:虽然在转移时要枚举一层 \(sz_u\) 还要枚举一层 \(sz_v\),但是每次都是先转移再累加 \(sz_v\),也就是从 \(v\) 的子树中选点和 \(v\) 旁边的子树选点进行匹配。每一对选出的点都只会在他们的 lca 处被计算一次,故总的复杂度是 \(O(n^2)\)。

code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=5e3+5,mod=1e9+7;
int n,sz[N];
ll f[N][N],sum[N],tmp[N];
vector<int>e[N];
void dfs(int u,int fa){
	sz[u]=1;
	f[u][1]=1;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
		for(int i=1;i<=sz[u]+sz[v];++i)tmp[i]=0;
		for(int i=1;i<=sz[u];++i){
			for(int j=1;j<=sz[v];++j){
				tmp[i]=(tmp[i]+mod-f[u][i]*f[v][j]%mod*sum[j]%mod)%mod;
				tmp[i+j]=(tmp[i+j]+f[u][i]*f[v][j]%mod)%mod;
			}
		}
		for(int i=1;i<=sz[u]+sz[v];++i)f[u][i]=tmp[i];
		sz[u]+=sz[v];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;++i){
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
		e[b].pb(a);
	}
	sum[0]=1;
	for(int i=2;i<=n;i+=2)sum[i]=sum[i-2]*(i-1)%mod;
	dfs(1,0);
	ll ans=0;
	for(int i=1;i<=n;++i)ans=(ans+f[1][i]*sum[i]%mod)%mod;
	cout<<ans;
}

标签:sz,连通,int,配对,sum,Tree,times,ARC101E,Ribbons
From: https://www.cnblogs.com/sunsetlake/p/17989750

相关文章

  • CF1917F Construct Tree
    Link:http://codeforces.com/problemset/problem/1917/F知识点:背包,构造简述\(T\)组数据,每组数据给定参数\(d\)与一长度为\(n\)的数列\(l\),仅需判断是否可以构造出一棵树,满足:树的所有边长与数列元素一一对应。树的直径为\(d\)。\(1\leT\le250\),\(2\len\le2000\)......
  • Link-cut Tree
    这可能是我第一次学数据结构如此绝望链剖分重链剖分使用静态数据结构维护实链剖分(LCT)使用splay维护对每个节点,选择一个儿子作为实边,其他为虚边实链用splay维护虚边认父不认子,连接两个splay长链剖分查询修改链上信息随意换根动态维护连通性LCT核心操作access(x)从指......
  • C# AVEVA MARINE DRAWING TREE VIEW 快速读取方法,速度真的很快
    一般来讲我们使用MARAPI里面的ElementChildFirstGet和ElementSiblingNextGet函数去遍历而获得图元'''<summary>'''获取当前视图的全部的子视图的句柄'''</summary>'''<paramname="draftApp">M......
  • ABC337G Tree Inversion
    思路对于每个\(1\lei\len\)的\(i\)都要求答案,那我们考虑dp,去思考如何转移\(f_i\)。先不考虑全局,只考虑子树内的贡献,设\(g_u\)表示以\(u\)为根的子树内,对\(u\)来说满足条件的点对数。对于\(u\)的儿子\(v\),对\(v\)来说合法那么对\(u\)来说也一定合法。因为......
  • openGauss学习笔记-207 openGauss 数据库运维-常见故障定位案例-btree 索引故障情况下
    openGauss学习笔记-207openGauss数据库运维-常见故障定位案例-btree索引故障情况下应对策略207.1btree索引故障情况下应对策略207.1.1问题现象偶发索引丢失错误,报错如下。ERROR:index'xxxx_index'containsunexpectedzeropage或ERROR:index'pg_xxxx_index'cont......
  • 《Visual Tree Convolutional Neural Network in Image Classification》阅读笔记
    论文标题《VisualTreeConvolutionalNeuralNetworkinImageClassification》图像分类中的视觉树卷积神经网络作者YuntaoLiu、YongDou、RuochunJin和PengQiao来自国防科技大学并行和分布式处理国家实验室初读摘要问题:在图像分类领域,随着深度学习的快速发展,卷......
  • centos 离线安装tree命令
    在线安装tree命令:yum-yinstalltree 但是在线包总是下载失败:RepositoryepelislistedmorethanonceintheconfigurationRepositoryepel-debuginfoislistedmorethanonceintheconfigurationRepositoryepel-sourceislistedmorethanonceinthecon......
  • Electron 解决 connect ETIMEDOUT 或 sill idealTree buildDeps
    参考https://blog.csdn.net/Johanna51/article/details/123360477https://www.electronjs.org/zh/docs/latest/tutorial/installationhttps://cloud.tencent.com/developer/article/1781066环境环境版本说明Windows10nodev20.11.0npm10.2.4Windows......
  • CodeForces 1010F Tree
    洛谷传送门CF传送门educational的。另一道类似的题是[ABC269Ex]Antichain(但是我还没写)。考虑令\(b_u=a_u-\sum\limits_{v\inson_u}a_v\)。那么\(\sum\limits_{i=1}^nb_i=a_1=x\),且\(\foralli\in[1,n],b_i\ge0\)。所以最后连通块内有\(y\)个点,那......
  • 「笔记」dsu on tree
    目录写在前面引入树上启发式合并代码复杂度分析例题CF570DTreeRequestsCF600ELomsatgelralCF1709EXORTree写在最后写在前面高产似那啥。还以为这东西是啥科技呃呃,原来是能证明复杂度的乱搞。所以重链剖分就是动态dsu(精神错乱引入dsuontree,即树上启发式合并。启发......