这是一道多源最短路bfs问题来着，首先先用邻接表进行常规的建图，然后开一个dis数组用于记录每个点离Sekai点的距离（同时充当了类似vis数组判别一个点是否被遍历过的作用）。由于题目里需要找到只有一条边的点（Sekai点），所以再开一个deg数组统计每个点的度数，遍历一遍，把deg[i] = 1的
展开全文
根据题意，我们需要找到与相距最近的 Sekai 点距离最大的点且不是Sekai点的点容易得出,我们要求出每个点距离Sekai点的最短距离，有点像最短路问题，我们将所有Sekai点当作源点进行bfs创建一个dist数组初始化为INF，如果一个点的出度为1，那这个点就是Sekai点，我们就将这个点放入队
展开全文
题目链接
世界树上找米库
题目描述
在一个由 个地点和 条道路构成的树形结构中，我们需要找到所有“Miku”点。
Sekai 点：只连接一条道路的地点，即树的叶子节点（度为 1）。
Miku 点：必须满足两个条件：
它不能是 Sekai 点（度大于 1）。
在所有非 Sekai 点中，它到最
展开全文
题目链接
世界树上找米库
题目描述
给定一棵 个点、 条边的无根树。若某点度数为 ，称为 Sekai 点（叶子）。Miku 点需满足：
不是 Sekai 点；
在所有满足上一条件的点中，其到最近 Sekai 点的距离最大。
要求输出每组数据中所有的 Miku 点。
输入：
第一行一个整数 ，
展开全文
import sys
from collections import deque
def main():
sys.setrecursionlimit(1 << 25)
T = int(sys.stdin.readline())
for _ in ran
展开全文
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int t;
cin &
展开全文
本题的本质是一个典型的无向树上最短路径极值问题。
拓扑结构映射：
给定结构为 个节点、 条边的连通图，保证了其无根树（Unrooted Tree）的严格数学性质。
Sekai 点的定义“只延伸出一条道路的地点”，在图论中等价于树的叶子节点（度数为 1 的节点）。
Miku 点的定义为：在非叶子节
展开全文
多源bfs（Modern Cpp）
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
constexpr int inf = 1E9;
void
展开全文
思路：多源bfs。首先我们要弄清楚Sekai点是什么？其实就是度数为1的叶子节点，我们要找与Sekai点相距最近的最大距离Miku点，就只需要把所有Sekai点收集起来，做一个多源bfs，就可以得到Sekai点到其他Miku点的最短距离。然后统计其中的最大值及其出现次数，并且根据要求输出答案即可
代
展开全文
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5,inf=1e9+7;
// 全局变量说明：
// dist[i]：节点i到最近叶子节点的最短距离，初始为无穷大
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
