Cf D. Nauuo and Circle
2024-09-03 15:51:32
https://codeforces.com/contest/1173/problem/D
题意:
给出你一个包含 n 个点的树,这 n 个点编号为 1~n;
给出一个圆,圆上放置 n 个位置,第 i 个位置对应树中的某个节点,并且不重复;
求在圆上还原这棵树后,使得边不相交的总方案数;
学习出:https://www.cnblogs.com/violet-acmer/p/10991346.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=;
const int M=2e5+;
struct node{
int nextt,v;
}e[M<<];
vector<int>son[M];
int head[M],n,tot;
ll fac[M],dp[M];
void addedge(int u,int v){
e[tot].v=v;
e[tot].nextt=head[u];
head[u]=tot++;
}
void dfs(int u,int f){
for(int i=head[u];~i;i=e[i].nextt){
int v=e[i].v;
if(v==f)
continue;
son[u].push_back(v);
dfs(v,u);
}
int flag=;
if(u!=)
flag=;
int k=son[u].size()+flag;
dp[u]=fac[k];
for(int i=;i<son[u].size();i++){
dp[u]=dp[u]*dp[son[u][i]]%mod;
}
}
ll solve(){
dfs(,);
return dp[]*n%mod;
}
int main(){
scanf("%d",&n);
fac[]=;
for(int i=;i<=n;i++)
fac[i]=(i*fac[i-])%mod;
memset(head,-,sizeof(head));
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
printf("%I64d",solve());
return ;
}
最新文章
- php实现设计模式之 职责链模式
- [HTML5]HTML结构性元素(Structure)
- 【001:转载 eclipse中颜色的设置】
- MongoDB中的字段类型Id
- 微信公众平台项目中遇到的小问题40016,Invalid button size
- 使用fsck修复文件系统错误
- markdown to html
- mybaits 学习
- 转载.NET 4.0中的泛型的协变和逆变
- OpenGL ES2.0基础入门
- 面试前的准备---C#知识点回顾----05
- 系统分层 manager层意义
- 智能电视TV开发---直播视频客户端结构设计和实现
- 开源TinyXML 最简单的新手教程
- ERROR 1044 (42000): Access denied for user &#39;&#39;@&#39;localhost&#39; to database &#39;mysql&#39; mysql>; use mysql
- 前端笔记之JavaScript面向对象(四)组件化开发&;轮播图|俄罗斯方块实战
- 日志分析工具 Log Parser
- Unity项目架构设计与开发管理 学习
- google浏览器window.onbeforeunload方法兼容问题
- C#基础第一天-作业答案
热门文章
- codeforces 596 C. p-binary
- HTML 回到顶部 浮动
- opencv显示图像
- HDU-2087 C - 剪花布条(KMP基本)
- 经理人和app开发者大打出手,说明这个市场已经畸形变态?
- MyBatis+SpringMVC 框架搭建小结
- 2019牛客暑期多校训练营(第七场)A.String【最小表示法】
- 感知机分类(perceptron classification)
- Android studio中2种build.gradle文件介绍
- 图形化编程娱乐于教,Kittenblock实例,图章效果的音乐画面