首页 > 其他分享 >AGC058 F Authentic Tree DP

AGC058 F Authentic Tree DP

时间:2023-09-14 16:55:26浏览次数:52  
标签:frac 笛卡尔 拓扑 Tree 边点 树形 AGC058 Authentic 我们

一道问号题,AT 赛场上没人通过。其实是联考题

这道题十分有意思,做法很简单但是要想到是极其困难的。考场上我也拿着推了很久猜测这个式子的组合意义,擦到了正解的一些边。然而正解的思想还是太反直觉了。

首先题目中的式子实际上是让我们对树上的边建一颗笛卡尔树,然后计算笛卡尔树所有子树大小 +1 的倒数乘积之和。

如果没有这个 +1 一切多么美好啊!相当于给边集随一个排列,然后用这个排列建笛卡尔树,众所周知由于树形拓扑序就是 \(\prod_u \frac{1}{sz_u}\),所以我们只需要求出满足树形拓扑序的排列的出现概率就行了。推出来发现答案永远是 1

同样的我们考虑用类似的方法对本题搞事情,我们对每一个边和点都建出点,有人会说:你这样点数还是不是 \(n\) 啊,所以我们再给每一个边点下面接 \(P-1\) 个叶子,那么在模意义下计算出来的 \(\frac{1}{n}\) 就是一模一样的了!

我们考虑同样对我们建出来的这些点随权值。树上笛卡尔树的建法是找到每个连通块中权值最小的那个点,而这里修改一下建法,如果权值最小的那个点不是边点的话,定义整个过程就失败了,否则就删掉对应的边递归下去,那么每个连通块不失败的概率就是题目中要求 \(\frac{1}{n}\)。我们发现对于一种赋权方案,过程最终不会失败当且仅当每一个边点都比相邻的点小,于是我们只要对这个东西计数就是答案了。

我们对每一个边点向父亲的连边直接容斥,发现就成了若干个森林的拓扑序方案,也是 \(\prod_u \frac{1}{sz_u}\),树形背包就做完了!!!

#include <cstdio>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=5003,P=998244353;
typedef long long ll;
int n;
int hd[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){
	nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;
}
int f[N][N],sz[N],tmp[N],inv[N];
void dfs(int u,int fa){
	f[u][sz[u]=1]=1;
	for(int i=hd[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa) continue;
		dfs(v,u);
		long long sum=0;
		for(int j=1;j<=sz[v];++j) sum+=f[v][j];
		for(int j=1;j<=sz[u];++j)
			for(int k=1;k<=sz[v];++k)
				tmp[j+k]=(tmp[j+k]+(ll)f[u][j]*f[v][k])%P;
		sz[u]+=sz[v];
		for(int j=1;j<=sz[u];++j){
			f[u][j]=(sum%P*f[u][j]-tmp[j])%P;
			if(f[u][j]<0) f[u][j]+=P;
			tmp[j]=0;
		}
	}
	for(int i=1;i<=sz[u];++i){
		f[u][i]=(ll)f[u][i]*inv[i]%P;
		if(fa) f[u][i]=(ll)f[u][i]*inv[i]%P;
	}
}
int main(){
	n=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	inv[1]=1;
	for(int i=2;i<=n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
	dfs(1,0);
	long long res=0;
	for(int i=1;i<=n;++i) res+=f[1][i];
	printf("%d\n",int(res%P));
	return 0;
}

标签:frac,笛卡尔,拓扑,Tree,边点,树形,AGC058,Authentic,我们
From: https://www.cnblogs.com/yyyyxh/p/agc058_f.html

相关文章

  • TreeView的基本使用,以及和TableView的区别
    Qt中的QTreeView是一个用于显示树形数据的强大控件,通常用于显示层次结构数据。以下是使用QTreeView的基本步骤:创建一个QTreeView实例:在你的主窗口或其他窗口部件中创建一个QTreeView实例:QTreeView*treeView=newQTreeView(this);创建一个数据模型:QTreeView需要一个数......
  • 1135 Is It A Red-Black Tree
    题目:Thereisakindofbalancedbinarysearchtreenamed red-blacktree inthedatastructure.Ithasthefollowing5properties:(1)Everynodeiseitherredorblack.(2)Therootisblack.(3)Everyleaf(NULL)isblack.(4)Ifanodeisred,thenbot......
  • Java树形菜单_轻量级js树形插件_jsTree树形插件
    //插件效果//代码<!DOCTYPEhtml><html><head><title>JS轻量级树形插件</title><metacharset="utf-8"><linkrel="stylesheet"href="https://cdnjs.cloudflare.com/ajax/libs/jstree/3.2.1/themes/def......
  • 界面控件DevExpress WPF TreeMap,轻松可视化复杂的分层结构数据!
    DevExpressWPF TreeMap控件允许用户使用嵌套的矩形块可视化复杂的平面或分层结构数据。P.S:DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的......
  • 平衡二叉树(Balanced Binary Tree)
    平衡二叉树(BalancedBinaryTree)平衡二叉树是一种特殊的二叉搜索树,它具有以下特点:每个节点的左子树和右子树的高度差不超过1。所有的子树也都是平衡二叉树。通过保持平衡性,平衡二叉树可以在最坏情况下仍然具有较好的性能,保证查找、插入和删除操作的时间复杂度为O(logn)。......
  • 二叉树 遍历 hdu-1710-Binary Tree Traversals
    给出二叉树的前序遍历和中序遍历,求后序遍历。。 算法:由前序遍历的第一个元素可确定左、右子树的根节点,参照中序遍历又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列,最终构造出二叉树。 由前序和中序结果求后序遍历结果树的遍历: 给你一棵树的先......
  • 二叉搜索树(Binary Search Tree,BST)
    二叉搜索树(BinarySearchTree,BST)二叉搜索树(BinarySearchTree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质对于二叉搜索树的每个节点左子树中的所有节点的值都小于该节点的值右子树中的所有节点的值都大于(或等于)该节点的值对于二叉搜索树的任意节点,其......
  • 二叉树(binary tree)
    二叉树(binarytree)二叉树(BinaryTree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点:每个节点最多有两个子节点,分别称为左子节点和右子节点。左子树和右子树也是二叉树,它们的结构与父节点类似。二叉树的顺......
  • QtreeWidget的部分基本使用
    创建树节点(QTreeWidgetItem)并添加到QTreeWidget中://创建子节点QTreeWidgetItem*child1=newQTreeWidgetItem(root);child1->setText(0,"子节点1");child1->setText(1,"子节点1的列2内容");QTreeWidgetItem*child2=newQTreeWidgetItem(root);child2->......
  • 如何设置el-tree点箭头图标才会展开或者收起(XTHS实测)
    在使用Element框架开发vue项目时,如何设置el-tree只有点击箭头图标才会展开或者收起效果呢?如图 转自:如何设置el-tree点箭头图标才会展开或者收起-百度经验(baidu.com)......