【练习】树形dp
G. Group Homework
time limit per test: 3 s
memory limit per test: 512 MB
input: standard input
output: standard output
No, we don’t want group homework. It’s the place where KaTeX parse error: Expected 'EOF', got '&' at position 7: 1 + 1 &̲lt; 1 can be true. However, you are currently the leader of a group with three members. Luckily, your group members will write everything down for you since you are the prestigious leader. Unluckily, you have to assign the new algorithm homework to your two team members, Mr. Dian and Mr. Beng, who can’t understand the ideas of each other correctly and mess up all the details in the cooperation.
The new homework is about a tree: there are n n n vertices on the tree with n − 1 n - 1 n−1 bidirectional edges connecting them. Each vertex i i i is a problem with a score of a i a_i ai. You can assign a tree path to each member, then Mr. Dian and Mr. Beng will solve the problems on their path independently. The final score of the homework is decided by the sum of the scores of the vertices visited by exactly one member — as we mentioned before, if both of them solved one problem independently, they will argue a lot about who is right, and all the effort will be in vain.
Now, you — Mr. Ji — want to maximize the final score (as well as the chance not to drop out of school due to too low GPA). Make a wise choice!
Input
The first line of input contains a single integer n ( 1 ≤ n ≤ 2 × 1 0 5 ) n\, (1 \leq n \leq 2 \times 10^5) n(1≤n≤2×105), denoting the number of vertices.
The second line contains n n n integers separated by spaces, the i i i-th integer denotes a i ( 1 ≤ a i ≤ 1 0 4 ) a_i\, (1 \leq a_i \leq 10^4) ai(1≤ai≤104).
In the following n − 1 n - 1 n−1 lines, each contains two integers u , v ( 1 ≤ u , v ≤ n ) u, v\, (1 \leq u, v \leq n) u,v(1≤u,v≤n), denoting ( u , v ) (u, v) (u,v) is a tree edge.
It is guaranteed that the input edges form a tree of n n n vertices.
https://www.cnblogs.com/hbhhbh/articles/16858850.html
#include<iostream>
using namespace std;
#include<vector>
#include<map>
#include<algorithm>
const int N=200010;
int n;
vector<int> G[N];
map<int,int> dp1[N];
map<int,int> dp2[N];
int w[N];
//u到子树中最长路径
int dfs1(int u,int fa)
{if(dp1[u][fa])return dp1[u][fa];int xuan=w[u];for(int v:G[u]){if(v==fa)continue;xuan=max(xuan,dfs1(v,u)+w[u]);}return dp1[u][fa]=xuan;
}//dp2 u韦根的子树中,两点间路径,最长
int dfs2(int u,int fa){if(dp2[u][fa])return dp2[u][fa];int xuan=0;int d1=0;int d2=0;for(auto v:G[u]){if(v==fa)continue;//子树中,不经过uxuan=max(xuan,dfs2(v,u));//经过uint t=dfs1(v,u);if(d1<t){d2=d1;d1=t;}else if(d2<t){d2=t;}}
xuan=max(xuan,d1+d2+w[u]);
return dp2[u][fa]=xuan;
}int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);
}int ans=0;
for(int i=1;i<=n;i++){vector<int> l={0,0,0,0};for(auto v:G[i])l.push_back(dfs1(v,i));sort(l.begin(),l.end());reverse(l.begin(),l.end());ans=max(ans,l[0]+l[1]+l[2]+l[3]);
}
for(int i=1;i<=n;i++){for(auto v:G[i]){int t1=dfs2(v,i);int t2=dfs2(i,v);ans=max(ans,t1+t2);}
}
cout<<ans;}
I. Infection
I. Infection
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
A highly propagating bacterium infects a tree of n n n nodes (with n − 1 n-1 n−1 edges, no cycles). These nodes are indexed from 1 1 1 to n n n.
Exactly one node will be infected at the beginning. Each node on the tree has an initial susceptibility weight a i a_i ai, which represents that node i i i has a probability of a i ∑ i = 1 n a i \dfrac{a_i}{\sum_{i=1}^{n}a_i} ∑i=1naiai to become the initial infected node of the tree.
In addition, each node has an infection probability p i p_i pi, which represents its probability of being infected by adjacent nodes.
Specifically, starting from the initial infected node, if a node is infected, the uninfected node x x x that is adjacent to it will have a probability of p x p_x px to become a new infected node, and then x x x can continue to infect its adjacent nodes.
Now, your task is to calculate the probability that exactly k k k nodes are eventually infected. You need to output an answer for each k = 1 , … , n k=1,\ldots, n k=1,…,n.
You need to output the answer modulo 1 0 9 + 7 10^9+7 109+7, which means if your answer is a b \frac{a}{b} ba ( gcd ( a , b ) = 1 \gcd(a,b)=1 gcd(a,b)=1), you need to output a ⋅ b − 1 m o d 1 0 9 + 7 a\cdot b^{-1}\bmod{10^9+7} a⋅b−1mod109+7, where b ⋅ b − 1 ≡ 1 ( m o d 1 0 9 + 7 ) b\cdot b^{-1} \equiv 1 \pmod{10^9+7} b⋅b−1≡1(mod109+7).
Input
The first line contains an integer n n n ( 2 ≤ n ≤ 2 000 2\leq n \leq 2\,000 2≤n≤2000), denoting the number of nodes of the tree.
The next n − 1 n-1 n−1 lines, each line contains two positive integers u u u and v v v ( 1 ≤ u , v ≤ n 1\leq u,v\leq n 1≤u,v≤n), denoting that there is an edge ( u , v ) (u,v) (u,v) on the tree.
Next n n n lines, the i i i-th line contains three positive integers a i , b i , c i a_i, b_i, c_i ai,bi,ci, where a i a_i ai means as above and p i = b i c i p_i=\frac{b_i}{c_i} pi=cibi. It is guaranteed that 1 ≤ a i , b i , c i ≤ 1 0 9 , ∑ i = 1 n a i ≤ 1 0 9 , b i ≤ c i , gcd ( b i , c i ) = 1 1\leq a_i, b_i, c_i \leq 10^9, \displaystyle \sum_{i=1}^{n}a_i\leq 10^9, b_i\leq c_i, \gcd(b_i,c_i)=1 1≤ai,bi,ci≤109,i=1∑nai≤109,bi≤ci,gcd(bi,ci)=1.
Output
Output n n n lines, each line contains single integer. The integer on the i i i-th line should be the answer modulo 1 0 9 + 7 10^9+7 109+7 when k = i k=i k=i.
Example
Input
5
2 1
5 2
3 2
4 3
2 1 5
3 1 2
2 1 1
2 1 1
3 1 2
Output
208333335
166666668
166666668
950000007
508333337
https://blog.csdn.net/yingjiayu12/article/details/129073201
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
const int mod=1e9+7;
ll qpow(ll a,ll b) {ll ans=1;while(b) {if(b&1) ans=(ans*a)%mod;b>>=1;a=(a*a)%mod;}return ans;
}
vector<int>edge[maxn];
int a[maxn],b[maxn],c[maxn];int p[maxn];int ans[maxn];
int n;
int f[2010][2010],g[2010][2010];int Size[maxn];int sum=0;
int Temp1[maxn],Temp2[maxn];
//f不包括初始感染点,g包括初始感染点
void dfs(int u,int pre_u) {Size[u]=1;a[u]=a[u]*sum%mod;f[u][1]=p[u];g[u][1]=a[u];for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==pre_u) continue;dfs(v,u);for(int i=1;i<=Size[u]+Size[v];i++) {Temp1[i]=Temp2[i]=0;}for(int i=1;i<=Size[u];i++) {for(int j=0;j<=Size[v];j++) {Temp1[i+j]=(Temp1[i+j]+f[u][i]*f[v][j]%mod)%mod;Temp2[i+j]=(Temp2[i+j]+g[u][i]*f[v][j]%mod)%mod;if(j) Temp2[i+j]=(Temp2[i+j]+f[u][i]*g[v][j]%mod)%mod;}}Size[u]+=Size[v];for(int i=1;i<=Size[u];i++) {f[u][i]=Temp1[i];g[u][i]=Temp2[i];}}for(int i=1;i<=Size[u];i++) {ans[i]=(ans[i]+(1-p[pre_u]+mod)%mod*g[u][i]%mod)%mod;}f[u][0]=(1-p[u]+mod)%mod;
}
signed main() {n=read();for(int i=1;i<=n-1;i++) {int u=read(),v=read();edge[u].push_back(v);edge[v].push_back(u);}for(int i=1;i<=n;i++) {a[i]=read();b[i]=read();c[i]=read();p[i]=b[i]*qpow(c[i],mod-2)%mod;sum=(sum+a[i])%mod;}sum=qpow(sum,mod-2);dfs(1,0);for(int i=1;i<=n;i++) cout<<ans[i]<<endl;return 0;
}
相关文章:
【练习】树形dp
G. Group Homework time limit per test: 3 s memory limit per test: 512 MB input: standard input output: standard output No, we don’t want group homework. It’s the place where KaTeX parse error: Expected EOF, got & at position 7: 1 1 &̲lt; 1 …...

Mybatis是如何进行分页的?
大家好,我是锋哥。今天分享关于【Mybatis是如何进行分页的?】面试题。希望对大家有帮助; Mybatis是如何进行分页的? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 MyBatis 实现分页的方式有很多种,最常见…...
【新春特辑】2025年春节技术展望:蛇年里的科技创新与趋势预测
🔥【新春特辑】2025年春节技术展望:蛇年里的科技创新与趋势预测 📅 发布日期:2025年01月29日(大年初一) 在这个辞旧迎新的美好时刻,我们迎来了充满希望的2025年,也是十二生肖中的蛇…...

论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(五)
Understanding Diffusion Models: A Unified Perspective(五) 文章概括基于得分的生成模型(Score-based Generative Models) 文章概括 引用: article{luo2022understanding,title{Understanding diffusion models: A…...

C++并发:C++内存模型和原子操作
C11引入了新的线程感知内存模型。内存模型精确定义了基础构建单元应当如何被运转。 1 内存模型基础 内存模型牵涉两个方面:基本结构和并发。 基本结构关系到整个程序在内存中的布局。 1.1 对象和内存区域 C的数据包括: 内建基本类型:int&…...

JavaScript函数中this的指向
总结:谁调用我,我就指向谁(es6箭头函数不算) 一、ES6之前 每一个函数内部都有一个关键字是 this ,可以直接使用 重点: 函数内部的 this 只和函数的调用方式有关系,和函数的定义方式没有关系 …...
【java学习笔记】@Autowired注解 使用方法和作用 | 配合@Component注解使用 | IOC控制反转
原本在类中,要用什么对象,就直接new一个对象。这种原始的方式 是由应用本身去控制实例的。 用了Autowired注解后,就相当于把实例(对象)的控制权 交给外部容器来统一管理(降低耦合)。(…...
数论问题76一一容斥原理
容斥原理是一种计数方法,用于计算多个集合的并集中元素的个数,以避免重复计算。以下是其基本内容及相关公式: 两个集合的容斥原理 若有集合A和集合B,那么A与B的并集中元素的个数等于A集合元素个数加上B集合元素个数,再…...

python-leetcode-从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right r…...

【Oracle篇】使用Hint对优化器的执行计划进行干预(含单表、多表、查询块、声明四大类Hint干预)
💫《博主介绍》:✨又是一天没白过,我是奈斯,从事IT领域✨ 💫《擅长领域》:✌️擅长阿里云AnalyticDB for MySQL(分布式数据仓库)、Oracle、MySQL、Linux、prometheus监控;并对SQLserver、NoSQL(…...

设置jmeter外观颜色
设置jmeter外观颜色 方法: 步骤一、点击顶部选项 ->外观,这里提供了不同的主题,可选自己喜欢的风格。 步骤二、选择后,弹框提示点击Yes。...

计算机网络 IP 网络层 2 (重置版)
IP的简介: IP 地址是互联网协议地址(Internet Protocol Address)的简称,是分配给连接到互联网的设备的唯一标识符,用于在网络中定位和通信。 IP编制的历史阶段: 1,分类的IP地址: …...

神经网络和深度学习
应用 类型 为什么近几年飞速发展 数据增长,算力增长,算法革新 逻辑回归 向量化 浅层神经网络(Shallow neural network) 单条训练数据前向传播计算表达式 batch训练数据前向传播计算表达式 反向传播计算表达式 参数随机初始化 不能全部设为0 原因是同一…...
MySQL 基础学习(3):排序查询和条件查询
MySQL 查询与条件操作:详解与技巧 在本文中,我们将探讨 MySQL 中的查询操作及其相关功能,包括别名、去重、排序查询和条件查询等,并总结一些最佳实践和注意事项。 一、使用别名(AS) 在查询中,…...

webAPI -DOM 相关知识点总结(非常细)
title: WebAPI语法 date: 2025-01-28 12:00:00 tags:- 前端 categories:- 前端WEB API 了解DOM的结构并掌握其基本的操作,体验 DOM 在开发中的作用 API简介 就是使用js来操作html和浏览器 什么是DOM? 就是一个文档对象模型,是用来呈现预计于任意htm…...
web集群
项目名称 基于keepalivednginx构建一个高可用、高性能的web集群 项目架构图 项目描述 构建一个基于nginx的7层负载均衡的web集群项目,模拟企业的业务环境达到构建一个高并发、高可用的web集群。通过压力测试来检验整个集群的性能,找出瓶颈࿰…...

Elasticsearch——Elasticsearch性能优化实战
摘要 本文主要介绍了 Elasticsearch 性能优化的实战方法,从硬件配置优化、索引优化设置、查询方面优化、数据结构优化以及集群架构设计等五个方面进行了详细阐述,旨在帮助读者提升 Elasticsearch 的性能表现。 1. 硬件配置优化 升级硬件设备配置一直都…...

不背单词快捷键(不背单词键盘快捷键)
文章目录 不背单词快捷键 不背单词快捷键 ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ ᅟᅠ …...
kafka-保姆级配置说明(consumer)
bootstrap.servers #deserializer应该与producer保持对应 #key.deserializer #value.deserializer ##fetch请求返回时,至少获取的字节数,默认值为1 ##当数据量不足时,客户端请求将会阻塞 ##此值越大,客户端请求阻塞的时间越长&…...

1.五子棋对弈python解法——2024年省赛蓝桥杯真题
问题描述 原题传送门:1.五子棋对弈 - 蓝桥云课 "在五子棋的对弈中,友谊的小船说翻就翻?" 不!对小蓝和小桥来说,五子棋不仅是棋盘上的较量,更是心与心之间的沟通。这两位挚友秉承着"友谊第…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
游戏开发中常见的战斗数值英文缩写对照表
游戏开发中常见的战斗数值英文缩写对照表 基础属性(Basic Attributes) 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起,为了跨网段推流,千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...

Xcode 16.2 版本 pod init 报错
Xcode 版本升级到 16.2 后,项目执行 pod init 报错; ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchron…...