给出一棵树和一个图,问有多少种方法把树的节点标号使得其在改图中至少有一棵生成树与原来的树是重构的。
n<=17
想到了容斥,但是没想到从哪里容斥。。。
显然题目给了两个限制,一个是原树中的每条边都要在图中出现,一个是每个标号仅出现一次。
我们可以在必须满足第一个限制的前提下,对第二个限制进行容斥。
假设现在知道了那些号是不能标的,那么我们就可以通过树形dp来得到方案数:设f[i,j]表示节点i标号为j的方案数,然后枚举其儿子的方案数,转移随便搞即可。
那么答案就是随便标的方案数-1个标号不能用的方案数+2个标号不能用的方案数。。。。
为什么呢?
因为每个标号不能重复,那么就要用全部情况减去有重复的情况。如果有一个标号不能选,那就表明必然至少有一个会重复,所以正确性显然。
今天做了两道类似的题,一道是bzoj 4596: [Shoi2016]黑暗前的幻想乡,另一道就是这道啦。
方法都是容斥,那么我想总结一下类似题目的一般套路。
首先你得想得到要用容斥,可以记住某位大神所说的,看到计数想容斥。
然后找到题目所给的限制。bzoj 4596中的限制一个是必须是生成树,另一个是必须每条边属于不同的公司。这题的限制在上面。
那么我们就可以在满足题目所给的其余限制的前提下,对其中一个限制进行容斥,也就是先不管这个限制,再减去其不符合限制的答案即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=20;
int n,m,cnt,a1,a[N],last[N],map[N][N];
struct edge{
int to,next;}e[N*2];
LL ans,f[N][N];
void addedge(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void dp(int x,int fa,int s)
{
for (int i=last[x];i;i=e[i].next)
if (e[i].to!=fa) dp(e[i].to,x,s);
for (int i=1;i<=a1;i++)
{
f[x][i]=1;
for (int j=last[x];j;j=e[j].next)
{
if (e[j].to==fa) continue;
LL w=0;
for (int k=1;k<=a1;k++)
if (map[a[i]][a[k]]) w+=f[e[j].to][k];
f[x][i]*=w;
}
}
}
LL calc(int s)
{
a1=0;
for (int i=1;i<=n;i++) if (!(s&(1<<(i-1)))) a[++a1]=i;
dp(1,0,s);
LL ans=0;
for (int i=1;i<=a1;i++) ans+=f[1][i];
return ans;
}
void dfs(int x,int y,int s)
{
if (x>n)
{
ans+=y*calc(s);
return;
}
dfs(x+1,y,s);
dfs(x+1,-y,s+(1<<(x-1)));
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=map[y][x]=1;
}
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
}
dfs(1,1,0);
printf("%lld",ans);
return 0;
}
文章浏览阅读998次,点赞3次,收藏3次。spring-boot-maven-plugin报错背景:将JDK1.8更换为1.11之后,原本不报错的项目报错了,具体为在编译时报错java.lang.ExceptionInInitializerError。猜测这应该与更换JDK版本有关,所以做出如下修改:首先修改这个版本号:(直接找了版本最高的)问题来了,改变Lombok的版本之后,spring-boot-maven-plugin报错了,报错信息大致为:Plugin ‘org.springframework.boot:spring-boot-_spring-boot-maven-plugin报错
文章浏览阅读85次。原文地址:CRichEditCtrl系列讲堂9解决CEdit/CRichEdit中SetSel错位或者位置判断错误的问题作者:慢动作的猪需求:在CEdit中查找指定文本然后选中,当然CEdit中会包含汉子以及英文字符,也包括回车换行符,然后进行查找,第一次标识并选中第一次出现的位置,再次点查找要标识并选中第二次出现位置,如果到达最后一次要从头重新查找。解答:问题很简单可能会使用..._cricheditctrl cedit
文章浏览阅读5.7k次。<template><section><el-buttonv-if="fileName"type="text"@click="handelReplace"class="l-h-20">重新上传</el-button><el-uploadv-show="!fileName"class="upload-wrapm-r-5"ref="uploadBox"a..._this.$refs.upload
文章浏览阅读1.6k次。1.怎样定义网页语言(字符集)? 在制作网页过程中,你首先要定义网页语言,以便访问者浏览器自动设置语言,而我们用所见即所得的HTML工具时,都没有注意到这个问题,因为它是默认设置。要设置的语言可以在HTML代码状态下找到: 把charset=gb2312改换成其它语言代码即可,比如英文harset=en. 2.怎样防止别人把你的网页放到框架里?_怎样在网页中加入email链接并显示预定的主题?
文章浏览阅读225次。一、要解决什么样的问题?在写这个函数之前,有位童鞋在群里问如何纯前端严格验证图片格式。这在html5时代之前,那是不可能实现的,必须要上传到后台,由后台脚本读取文本流后进一步验证。这样就造成了一定的服务器资源浪费。但是html5时代,这个工作我们完全可以交给前端来做了。另一方面,html5时代,许多我们原来的图片预览方案都失效了。究其原因,其实是现代浏览器出于对用户隐私的保护,file控件不再提供..._图片上传识别的html
文章浏览阅读435次。函数一:学习目的1:正确理解函数在C语言程序设计中的作用和地位。2:熟悉函数的定义、原型声明和调用的方法。3:熟悉数组名做函数参数的用法二:学习准备1:有一个一维数组score,内放10个学生成绩,求平均成绩。#include void main(){ float average(float array[10]);float score[10],aver; int i;printf("input..._c语言中的small关键字
文章浏览阅读287次。我们一直用GitHub作为免费的远程仓库,如果是个人的开源项目,放到GitHub上是完全没有问题的。其实GitHub还是一个开源协作社区,通过GitHub,既可以让别人参与你的开源项目,也可以参与别人的开源项目。在GitHub出现以前,开源项目开源容易,但让广大人民群众参与进来比较困难,因为要参与,就要提交代码,而给每个想提交代码的群众都开一个账号那是不现实的,因此,群众也仅限于报个bug_qcap使用教程
文章浏览阅读101次。java ziputilimport java.io.BufferedInputStream;import java.io.BufferedOutputStream;import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.IOException;i..._java hutool 压缩解压缩
文章浏览阅读3.7k次。深度强化学习实验室原文来源:https://arxiv.org/pdf/1708.07902.pdf翻译作者:梁天新博士编辑:DeepRL在本文中,我们将回顾最近的Deep Learni..._bhatti, s., desmaison, a., miksik, o., nardelli, n., siddharth, n., and torr
文章浏览阅读294次。Created by Jerry Wang, last modified on Sep 20, 2014在编辑individual object试图save的时候,遇到如下error message:debug 发现partnerSPRO里找到对应的customizing:..._less-error-message
文章浏览阅读672次。mkdir okadaGocd okadaGocnpm init转载地址:https://www.jianshu.com/p/a6d430a00242_node.js jest mocha
文章浏览阅读489次,点赞3次,收藏2次。小书童——凯撒密码题目链接:https://www.luogu.com.cn/problem/P1914题目背景某蒟蒻迷上了“小书童”,有一天登陆时忘记密码了(他没绑定邮箱or手机),于是便把问题抛给了神犇你。题目描述蒟蒻虽然忘记密码,但他还记得密码是由一个字符串组成。密码是由原文字符串(由不超过 50 个小写字母组成)中每个字母向后移动 nn 位形成的。z 的下一个字母是 a,如此循环。他现在找到了移动前的原文字符串及 nn,请你求出密码。输入格式第一行:n。第二行:未移动前的一串字母输出_java求凯撒密码某蒟蒻迷上了“小书童”,有一天登陆时忘记密码了(他没绑定邮箱