首页 > 试题广场 >

Alliances

[编程题]Alliances
  • 热度指数：10 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，
即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。
当一些帮派结成联盟时，他们会更加强大，同时也更加危险。他们所控制的城市数会显著增加。具体地，一个联盟控制的城市是联盟中所有帮派所占据的城市，再加上这些城市两两之间路径上的所有城市。
shy是树国的市长，他想要选择一个城市作为首都。在决定之前，他要先做一些调研。为此，他找来你帮他回答一些询问，你能做到吗？在每个询问中，shy会选择一个城市作为首都，同时会告诉你当前活跃的帮派的集合。在这个询问中，你只需要考虑给定的集合中的帮派，其他的帮派你可以当作不存在。已知给定集合中的这些帮派结成了联盟，shy希望抓获联盟中的人，以得到关于整个联盟的一些信息。为此，他要找到被联盟控制的所有城市中离首都最近的一座城市到首都的距离。有可能首都本身就被控制了，此时答案为0。请注意，询问之间相互独立，互不影响。


输入描述:
输入的第一行包含一个整数n，代表树国中的城市数。
 接下来n−1行，每行包含两个整数u和v，代表城市u和v之间存在一条道路。
 接下来一行包含一个整数k，代表树国中的帮派数。
 接下来k行，每行描述一个帮派。第i行的第一个整数c[i]代表第i个帮派占据的城市数，接下来c[i]个整数，代表被第i个帮派占据的城市。
 接下来一行包含一个整数Q，代表询问数。
 接下来Q行，每行描述一个询问。每行的前两个整数V和t[i]代表本次询问中的首都与需要考虑的帮派集合的大小。接下来t[i]个整数代表本次询问中需要考虑的帮派。.


输出描述:
对于每个询问，输出一行，包含一个整数，代表询问的答案。
示例1

输入

7
1 2
1 3
2 4
2 5
3 6
3 7
2
2 6 7
1 4
3
5 1 2
1 1 1
5 2 1 2

输出

2
1
1

备注:
对于30%的数据，1≤n,k,Q≤1000, 1≤每个帮派占据城市数之和≤1000, 1≤每个询问中考虑的帮派数之和≤1000  对于60%的数据，1≤n,k,Q≤100000, 1≤每个帮派占据城市数之和≤100000, 1≤每个询问中考虑的帮派数之和≤100000 对于100%的数据，1≤n,k,Q≤500000, 1≤每个帮派占据城市数之和≤500000, 1≤每个询问中考虑的帮派数之和≤500000
算法知识视频讲解
开通博客
头像 num73
发表于 2020-07-08 22:26:40
题目描述： 一颗个节点的树。给定个点集（个帮派），编号为。第i个点集代表第i个帮派占据的点的集合。定义一个节点被占领当且仅当满足下面其中一个条件： 该结点被一个帮派所占据。 该结点位于被占领的两个结点的路径上。 Q个询问，每个询问给出一个点，一个数，和个数（），代表在这个询问中选取（）这个帮派， 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 zzugzx
发表于 2020-07-07 19:06:49
题目链接 题意：题解： AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #d 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 JQK2020
发表于 2020-07-08 18:52:59
问题描述 树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。 当一些帮派结成联盟时，他们会 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shyyhs
发表于 2021-01-22 13:17:40
前言: 这个每日一题对我来说稍微复杂了亿点点... 思路: 首先的题目的条件就是所有点的lca到所有点的路径都被标记了.我们要求点V到这些点集的一个最小距离. 假如这个点集的LCA和V的lca不是LCA的话,那么显然的一个结论距离就是V到lca的距离. 假如不是,那么V一定位于LCA的子树中.这是我 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Severus.
发表于 2020-07-08 20:32:44
题目描述 树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。当一些帮派结成联盟时，他们会 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 CoolGuang!
发表于 2020-07-09 01:14:55
题意简化： 首先给出一棵树，其次询问一个点集，求包含这个点集的最小生成树与询问点x的最短距离 题目思路 首先考虑，如何确定这个点集的最小生成树：首先跑一个LCA，找出所有点公共的LCA，那么这个最小生成树的点集根节点(也就可以确定了) 之后就可以考虑这两种情况： 1.如果询问点，不在这个子树内 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 hnust_yangyanjun
发表于 2020-07-11 18:43:06
题目：有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。有k个帮派，每个帮派占领ci个城市。帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？ 思路：在树 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 horz
发表于 2020-07-11 16:12:09
这题太变态了吧。 分析 我们预处理出每个帮派的lca节点，当帮派合并的时候，我们就可以求各个帮派的lca的节点。 假设首都节点是u,各个帮派的lca是pos，分两种情况 当lca(u,pos) ！= pos的时候，说明u不在pos的子树下，答案就是dis(u,pos)。 当lca(u,pos) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Z_L_G
发表于 2025-08-17 10:58:26
好复杂的一个题 题意 n个结点，形成一棵根为1的树 k个帮派，每个帮派会控制一些结点 帮派可能结盟，单个帮派也可自己结盟，结盟后任意两个被控制的结点之间的路径都被联盟控制 Q次询问，每次询问给出首都V和结盟的帮派，只需要考虑结盟的帮派 每次询问回答首都V到最近的被控制的城市的距离 思路 对于 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunsetcolors
发表于 2020-07-08 14:28:00
NC13950 Alliances 题目地址： https://ac.nowcoder.com/acm/problem/13950 基本思路： 我们先对题进行分析，如果不考虑联盟，只对单一的帮派来说，我们找距离首都最近的一个帮派。那么分情况讨论一下，如果首都不在这个帮派的的子树里，那么最短距 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
上传者：牛客301599号
难度：
3条回答 358浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Alliances

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号