洛谷 P4516 [JSOI2018] 潜入行动

题目来源于:洛谷

题目本质:背包,树形dp

解题思路:

假设当前合并两个背包f[u][a][p1][q1] 和f[v][b][p2][q2] ,其中 v 是 u 的儿子。考虑合并后的f[u][a+b][p3][q3],q3 是合并后点 u 是否被监听,有两种情况:u 之前已经被监听,u 现在被 v 监听。即:q3=q1∣p2 。

完整代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const int mod=1000000007;
int N,K;
int f[MAXN][105][2][2];
int g[105][2][2];
int size[MAXN];
vector<int> G[MAXN];
int Mod(ll x,ll y){x%=mod,y%=mod;return (int)(x+y)%mod;
}
void dp(int u,int fa){size[u]=1;f[u][0][0][0]=f[u][1][1][0]=1;for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++){int v=*it;if(v==fa) continue;dp(v,u);for(register int i=0;i<=min(size[u],K);++i){g[i][0][0]=f[u][i][0][0],f[u][i][0][0]=0;g[i][0][1]=f[u][i][0][1],f[u][i][0][1]=0;g[i][1][0]=f[u][i][1][0],f[u][i][1][0]=0;g[i][1][1]=f[u][i][1][1],f[u][i][1][1]=0;}for(register int i=0;i<=min(size[u],K);++i){for(register int j=0;j<=min(size[v],K-i);++j){f[u][i+j][0][0]=Mod((ll)f[u][i+j][0][0],(ll)g[i][0][0]*(ll)f[v][j][0][1]);f[u][i+j][0][1]=Mod((ll)f[u][i+j][0][1],(ll)g[i][0][0]*(ll)f[v][j][1][1]+(ll)g[i][0][1]*((ll)f[v][j][1][1]+(ll)f[v][j][0][1]));f[u][i+j][1][0]=Mod((ll)f[u][i+j][1][0],(ll)g[i][1][0]*((ll)f[v][j][0][0]+(ll)f[v][j][0][1]));f[u][i+j][1][1]=Mod((ll)f[u][i+j][1][1],(ll)g[i][1][0]*((ll)f[v][j][1][0]+(ll)f[v][j][1][1])+(ll)g[i][1][1]*((ll)f[v][j][0][0]+(ll)f[v][j][0][1]+(ll)f[v][j][1][0]+(ll)f[v][j][1][1]));}}size[u]+=size[v];}
}
int main(){scanf("%d%d",&N,&K);for(register int i=1;i<N;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}dp(1,0);printf("%d",(int)(f[1][K][0][1]+f[1][K][1][1])%mod);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/406348.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用Java往Geoserver发布tif图层和shp图层

1. Maven依赖 栅格文件对应Tif文件 (即: 栅格就是tif) 矢量文件对应shp文件(即: 矢量就是shp) 注: 有的依赖可能在中央仓库及一些镜像仓库找不到需要手动指定仓库, 在依赖最下方 <!-- 中文转拼音工具类 --><dependency><groupId>com.belerweb</groupId&g…

简单步骤获取IP地址SSL 证书

在网络安全中&#xff0c;SSL证书在保护用户浏览器和Web服务器之间交换的敏感信息方面发挥着至关重要的作用。 但是&#xff0c;如果您不仅想保护域名&#xff0c;还想保护特定的IP地址&#xff0c;该怎么办&#xff1f;您可以为IP地址获取SSL证书吗&#xff1f; 简短的回答是…

.NET COER+CONSUL微服务项目在CENTOS环境下的部署实践

一、整体的环境安装与部署 1.1、DOCKER环境的部署 1.1.1 安装DOCKER yum install -y yum-utils device-mapper-persistent-data lvm2 yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo yum makecache fast && yu…

2024年【甘肃省安全员C证】考试题及甘肃省安全员C证考试总结

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 甘肃省安全员C证考试题考前必练&#xff01;安全生产模拟考试一点通每个月更新甘肃省安全员C证考试总结题目及答案&#xff01;多做几遍&#xff0c;其实通过甘肃省安全员C证模拟试题很简单。 1、【多选题】《安全生产…

企业要部署多点组网应该怎么做?

企业在进行扩张后&#xff0c;往往有建立多点组网的需求。本文将详细介绍企业怎样实现多点组网&#xff0c;以便有需要的用户进行了解和选择。 企业想要实现企业多点组网时&#xff0c;首先需要进行全面的网络规划和设计。这包括评估公司当前的网络架构、各个分支机构的地理位置…

AOP+ 自定义注解 +SpringElExpress自研缓存组件

AOP 自定义注解 SpringElExpress自研缓存组件 背景前置知识改造代码 背景 思考下这段代码&#xff0c;想想项目中是不是到处存在 先查缓存&#xff0c;缓存里面有&#xff0c;直接返回&#xff1b;缓存没有&#xff0c;查数据库&#xff0c;并更新到缓存 思考&#xff1a;如何…

区块链知识体系fisco-bcos实战

文章目录 一、区块链发展概述及类型和特征1.1 区块链的概念1.2 区块链的起源1.3 区块链的发展历程1.4 区块链的类型和特征 二、区块链的常见技术架构2.1 技术架构2.2 核心技术 三、区块链的常见应用3.1 生态环境监测3.2 医疗废弃物追踪解决3.3 区块链在电子政务领域的应用3.4 在…

mac安装ipa包【金铲铲为例】

mac安装ipa包 安装PlayCover 链接&#xff1a;https://github.com/PlayCover/PlayCover 1、点最新Releases 2、cmd ↓&#xff0c;拉到最下面下载dmg 3、安装 图标拖拽到Applications里 IPA下载 以金铲铲为例&#xff0c;良心砸壳包站点&#xff0c;有能力可以支持一下…

Modbus-TCP——Libmodbus安装和使用(Ubuntu22.04)

1、简介 Modbus是一种通信协议&#xff0c;广泛用于工业自动化和过程控制领域&#xff0c;允许不同设备之间进行数据交换。libmodbus是一个用于 Modbus 协议的开源库&#xff0c;主要用于开发和实现 Modbus 协议的客户端和服务器应用程序。libmodbus 以 C 语言编写&#xff0c…

Gartner发布2024年终端和工作空间安全成熟度曲线:24项相关技术发展和应用状况及趋势

由于攻击者使用人工智能来增强网络钓鱼和终端攻击&#xff0c;企业需要高级安全措施来阻止入侵行为。此技术成熟度曲线可帮助安全和风险管理领导者识别可增强终端和工作空间保护的技术。 需要知道什么 网络安全创新层出不穷&#xff0c;但区分真正的进步与短暂的趋势却很困难。…

66 IPV4/6 OSPFV2/3 实操

一 网络括谱图 二 IPV6 一 华为IPV6地址的配置思路 1 全局上开启IPV6功能 # ipv6 # 2 在指定的接口上配置IPV6地址上的接口上配置IPV6地址 ipv6 enable 3 在接口上配置IPV6地址 ipv6 address 2001:1::254/64 脚本 # interface GigabitEthernet0/0/1 ipv6 enable ip add…

Ajax基础案例

接口文档 欢迎使用 - AJAX阶段 地区查询 图解 代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewpor…

libLZMA库iOS18平台编译

1.下载xz源码: 使用autogen.sh生成configure文件 2.生成makefile rm -rf ./build/iOS && mkdir -p ./build/iOS && cd ./build/iOS && ../../configure --host=arm-apple-darwin64 --prefix=`pwd`/Frameworks/lzma CC="xcrun -sdk iphoneos cl…

熟悉Labview工具用

目录复制 目录 0.0&#xff1a;快捷键0.1&#xff1a;全局非图标显示0.2&#xff1a;小技巧&#xff1a;图片导入为程序1.2&#xff1a;事件结构1.2.0&#xff1a;超时分支&#xff1a;当事件结构框左上角设置为1时&#xff0c;单位毫秒&#xff0c;即理解为1ms内没有其他的事件…

ES+FileBeat+Kibana日志采集搭建体验

1.环境准备 需要linux操作系统&#xff0c;并安装了docker环境 此处使用虚拟机演示。&#xff08;虚拟机和docker看参考我之前写的文章&#xff09; VirtualBox安装Oracle Linux 7.9全流程-CSDN博客 VirtualBox上的Oracle Linux虚拟机安装Docker全流程-CSDN博客 简单演示搭建ES…

Linux_Shell三剑客grep,awk,sed-08

三剑客的概述&#xff1a; awk、grep、sed是linux操作文本的三大利器&#xff0c;合称文本三剑客&#xff0c;也是必须掌握的linux命令之一。三者的功能都是处理文本&#xff0c;但侧重点各不相同&#xff0c;其中属awk功能最强大&#xff0c;但也最复杂。grep更适合单纯的查找…

好用又便宜的平替苹果笔推荐:2024开学季盘点五款高性价比电容笔

​随着网络学习的不断发展&#xff0c;电容笔是一种常见的数字书写工具&#xff0c;受到许多学生党广泛欢迎&#xff0c;因为它可以与平板电脑完美配对&#xff0c;满足用户在平板上的书写、绘画等需求。可是原装笔的价格略贵&#xff0c;平替苹果笔的品牌又很多&#xff0c;很…

Java:循环练习

目录 1. 回文判断 2. 减法求商余 3. 求平方根 4.求质数 5. 猜数字 1. 回文判断 输入一个数字&#xff0c;判断是否为回文&#xff0c;回文就是正着读和反着读都一样&#xff0c;如121是回文&#xff0c;123则不是。 import java.util.Scanner;public class DemoNew {publ…

LUA的使用

背景 LUA刚流行起来的时候&#xff0c;想学习一下LUA。就找了一款使用LUA脚本引擎的游戏玩。希望从中了解LUA的使用 结果 熟悉了LUA的同时也熟悉了这款游戏。 准备工作 使用detoured withdll注入LUAK.dll。LUAK.dll用于管理LUA环境 procedure PROCESS_ATTACH(); stdcall …

Python 实现自定义异常

在Python编程中&#xff0c;异常处理是保证程序健壮性的重要机制。Python提供了一些内置的异常类&#xff0c;如ValueError、TypeError、IndexError等&#xff0c;开发者可以直接使用这些类来捕获和处理程序运行中出现的各种错误。然而&#xff0c;某些场景下&#xff0c;内置的…