第四届上海理工大学程序设计全国挑战赛 J.上学 题解 DFS 容斥

上学

题目描述

usst 小学里有 n 名学生,他们分别居住在 n 个地点,第 i 名学生居住在第 i 个地点,这些地点由 n−1 条双向道路连接,保证任意两个地点之间可以通过若干条双向道路抵达。学校则位于另外的第 0 个地点,第 0 个地点与第 1 个地点之间有另外一条双向道路链接。

最近学校开始启用校车来接学生上学,每一辆校车上都可以坐无限个学生,且每辆校车在一天内不会重复经过一条道路,校车终点始终为学校。每一位学生一天内只能乘坐一辆校车,且只能在自己居住的节点处上车,在学校下车。为了节省资金,学校会在保证每位学生都能坐上校车的前提下,安排最少数量的校车,每天早上从某些地点出发,并经过若干道路和地点最终抵达学校。第 x 位学生可以自由选择一辆经过第 x 个地点的校车,搭乘它到达学校。

现在学校想要从 n 个学生中选出 3 人参加某个比赛,但是学校不希望这 3 人之间太过 “熟悉”,请问一共有多少种不同的选人方案。

如果一种选择方案中, 3 个人可能在同一天里乘坐上同一辆校车,那就称这 3 个人之间太过 “熟悉”。

对于任意两个方案,如果存在一名学生在一个方案中且不在另一个方案中,那么就认为这两种方案不同。

输入描述

输入第 1 行包含 1 个正整数 n ,代表学生数量和学生居住的地点数量。( 3 ≤ n ≤ 2 × 1 0 5 3≤n≤2×10^5 3n2×105)

接下来 n−1 行每行有 2 个正整数 u, v ,代表第 u 个地点与第 v 个地点之间有一条双向道路。( 1 ≤ u , v ≤ n 1≤u,v≤n 1u,vn)

输出描述

输出一行,一个整数,代表选人方案数量。

样例输入 #1

5
1 2
2 3
3 4
4 5

样例输出 #1

0

样例输入 #2

5
1 2
2 3
2 4
1 5

样例输出 #2

8

原题

牛客——传送门

思路

根据题目描述可知,学校所选择的校车的路线是每个由叶子节点指向根节点(即节点1)的路径。题目目的是求出从 n 个学生中选择 3 个学生,保证 3 个学生不在同一条由叶子节点指向根节点(即节点1)的路径中的方案数。那么可以采用容斥原理,用不考虑 3 个学生在一条路径上的总的方案数减去 3 个学生在一条路径上的方案数。
求解示例如下:

对于上图所示的树,存在三条从叶子节点到根节点的路径,即 4-1,6-1,7-1,也就是三辆校车行驶的路线。首先,总的方案数为C(n,3)。而 3 个学生在一条路径上的方案数求解如下:C(4,3)+C(5,3)+C(5,3)-C(4,3)-C(3,3)。意思是4-1,6-1,7-1的三条路径中各自分别选取 3 个学生,但是存在重复选取5-1路径和3-1路径的情况。所以我们需要去重,即因为 5 节点下面有两条支链,所以要减去5-1路径的方案数乘以2-1(因为有两条支链,重复求了一次,所以2-1表示多求的数量)即减去C(4,3)。同理,还需要减去3-1路径的方案数即C(3,3)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 2e5 + 6;
vector<int> e[maxn];        // 邻接表存边
vector<pair<int, int>> num; // num.first为路径上的节点个数,num.second为该路径需要计算多少次void dfs(int p, int fa, int depth)
{if (p != 1 && e[p].size() <= 1) // 找到叶子节点{if (depth >= 3){num.push_back({depth, 1});}return;}int child_num = 0;                    // 支链数量,即孩子数量for (int i = 0; i < e[p].size(); i++) // 树的递归遍历{int v = e[p][i];if (v != fa){dfs(v, p, depth + 1);child_num++;}}if (depth >= 3) // 去重{num.push_back({-depth, child_num - 1}); // 加入num数组数指定为-depth,为的是做个标记}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n;cin >> n;for (int i = 1; i < n; i++){int u, v;cin >> u >> v;// 存无向边e[u].push_back(v);e[v].push_back(u);}dfs(1, 0, 1);// 先计算总方案数C(n,3)ll ans = n * (n - 1) * (n - 2) / 6;for (int i = 0; i < num.size(); i++){ll x = num[i].first;if (x > 0) // 若为正数,表示这是叶子节点到根节点的路径中选取学生的方案数ans -= x * (x - 1) * (x - 2) / 6;else // 标记为负数,表示这是要去重的路径中选取学生的方案数{x = -x;ans += x * (x - 1) * (x - 2) / 6 * (ll)num[i].second;}}cout << ans;return 0;
}

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

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

相关文章

【JAVA进阶篇教学】第十三篇:Java中volatile关键字讲解

博主打算从0-1讲解下java进阶篇教学&#xff0c;今天教学第十三篇&#xff1a;volatile关键字讲解。 在 Java 中&#xff0c;volatile关键字是一种轻量级的同步机制&#xff0c;用于确保变量的可见性和禁止指令重排序。本文将详细解释volatile关键字的工作原理、可见性保证以及…

Web安全:SQL注入之布尔盲注原理+步骤+实战操作

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…

ansible------inventory 主机清单

目录 inventory 中的变量 2&#xff09;组变量[webservers:vars] #表示为 webservers 组内所有主机定义变量&#xff0c;所有组内成 员都有效 ansible_userrootansible_passwordabc1234 3&#xff09; [all:vars…

实现字符串复制(C语言)

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 0;char a[100], b[100];//获取字符串&#xff1b;printf("请为数组a输入字符串…

回溯算法精讲

原理 回溯&#xff0c;就和深度优先遍历&#xff08;DFS&#xff09;类似&#xff0c;属于先一层到底直至到终点&#xff0c;如果这条路径不对&#xff0c;则回退一下&#xff0c;再继续往下搜索。 抽象地说&#xff0c;解决一个回溯问题&#xff0c;实际上就是遍历一棵决策树…

未来已来:Spring Cloud引领微服务新纪元

文章目录 1. 引言1.1 微服务架构的兴起与挑战1.2 引入Spring Cloud作为微服务解决方案的重要性 2. 背景介绍2.1 微服务架构概述2.2 Spring Cloud的定位2.3 Spring Cloud特性概览 3. Spring Cloud核心组件3.1 Eureka - 服务发现3.2 Hystrix - 断路器3.3 Ribbon - 客户端负载均衡…

Python vs MATLAB:选择深度学习的首选编程语言

Python vs MATLAB&#xff1a;选择深度学习的首选编程语言 在深度学习领域&#xff0c;编程语言的选择对于初学者的学习路径和未来的职业发展至关重要。目前&#xff0c;Python和MATLAB都是进行科学计算和数据分析的流行工具&#xff0c;但它们在深度学习社区中的应用和受欢迎…

构建教育新未来:智慧校园平台的深度解读与全景呈现

引言 在全球数字化转型的大潮中&#xff0c;智慧校园平台作为教育信息化的重要载体&#xff0c;正以前所未有的姿态颠覆传统的教育模式&#xff0c;引领教育行业步入一个崭新的时代。这个融合了大数据、人工智能、云计算、物联网等一系列前沿科技的平台&#xff0c;以其强大的功…

C++笔记:类和对象(一)

一.类的引入 1.类(class)是C中的一种特殊的数据结构&#xff0c;它封装了数据和操作这些数据的函数。 2.类中的数据被称为成员变量&#xff0c;而函数则被称为成员函数。 3.类可以被看作是一种模板&#xff0c;用于创建具有相同属性和行为的多个对象。 在C语言中结构体是一种复…

数字化运维体系:重塑IT运维的未来面貌

随着信息技术的飞速发展&#xff0c;传统运维模式已难以满足现代企业日益增长的复杂需求。在此背景下数字化运维体系应运而生&#xff0c;以其独特的视角和方法论为IT运维领域带来了革新性的变革。本文将深入探讨数字化运维体系的定义、核心要素&#xff0c;并阐述如何通过这一…

rust开发web服务器框架,github排名对比

Rocket Star最多的框架 github仓库地址&#xff1a;GitHub - rwf2/Rocket: A web framework for Rust. Rocket 是一个针对 Rust 的异步 Web 框架&#xff0c;重点关注可用性、安全性、可扩展性和速度。 Axum 异步运行时 githuh仓库地址&#xff1a;GitHub - tokio-rs/axum: …

Redis—图文详解高可用原因

本文不会讲解Redis的用途&#xff0c;关于用途会发另一片文章讲解&#xff0c;本文主要讲的是高可用的原理。 Redis高可用主要有以下三个原因&#xff1a;主从模式(上一篇讲Kafka的文章里有涉及到)&#xff0c;哨兵模式&#xff0c;Redis-Cluster(Redis集群)。 什么是主从模式…

【2024高校网络安全管理运维赛】巨细记录!

2024高校网络安全管理运维赛 文章目录 2024高校网络安全管理运维赛MISC签到考点&#xff1a;动态图片分帧提取 easyshell考点&#xff1a;流量分析 冰蝎3.0 Webphpsql考点&#xff1a;sql万能钥匙 fileit考点&#xff1a;xml注入 外带 Cryptosecretbit考点&#xff1a;代码阅读…

数据结构与算法-时间复杂度

这篇文章会讲到时间频度&#xff0c;时间复杂度&#xff0c;一些排序算法的平均时间复杂度与最坏时间复杂度 目录 1.度量一个程序&#xff08;算法&#xff09;的两种方法 1&#xff09;事后统计法 2&#xff09;事前估算法 2.时间频度 1.基本介绍 算法1&#xff1a; 算…

C语言 | Leetcode C语言题解之第86题分隔链表

题目&#xff1a; 题解&#xff1a; struct ListNode* partition(struct ListNode* head, int x) {struct ListNode* small malloc(sizeof(struct ListNode));struct ListNode* smallHead small;struct ListNode* large malloc(sizeof(struct ListNode));struct ListNode* …

SpringCloud微服务之Eureka、Ribbon、Nacos详解

SpringCloud微服务之Eureka、Ribbon、Nacos详解 1、认识微服务1.1、单体架构1.2、分布式架构1.3、微服务1.4、SpringCloud 2、服务拆分与远程调用2.1、服务拆分的原则2.2、服务拆分示例2.2、提供者与消费者 3、Eureka注册中心3.1、Eureka的结构和作用3.2、搭建eureka-server3.2…

使用IIS部署Vue项目

前提 使用IIS部署Vue项目&#xff0c;后端必须跨域&#xff0c;不要在Vue中用proxy跨域&#xff0c;那个只在dev环境中有用&#xff01; IIS安装&#xff0c;不用全部打勾&#xff0c;有些他默认就是方块 ■ 选择性安装的&#xff0c;就维持原样就可以。 添加网站配置 右键…

4.1 编写程序,从键盘接收一个小写字母,然后找出他的前导字符和后续字符,再按顺序显示这三个字符

方法一&#xff1a; 运行效果&#xff1a; 输入B&#xff0c;输出显示ABC&#xff1b;输入A&#xff0c;输出显示AB 思路&#xff1a; 1、通过键盘输入接收一个字母。 2、将输入的字母减去1&#xff0c;得到前导字符&#xff0c;然后输出。 3、将输入的字母加上1&#xff0c;得…

公有云Linux模拟UDP端口并抓包

目录 写在前面操作步骤服务端开启UDP端口并监听客户端连接Wireshark抓包查看 写在前面 关于具体的操作&#xff0c;请参考我的上一篇文章 公有云Linux模拟TCP三次挥手与四次握手&#xff08;Wireshark抓包验证版&#xff09; 在本文&#xff0c;仅介绍与上一篇不同的地方。 操…

机器学习特征降维

目录 特征降维概念 低方差过滤法 PCA主成分分析 相关系数法 小结 特征降维概念 特征对训练模型时非常重要的&#xff1b;用于训练的数据集包含一些不重要的特征&#xff0c;可能导致模型性能不好、泛化性能不佳&#xff1b;例如&#xff1a; 某些特征的取值较为接近&…