题目描述： 一颗个节点的树。给定个点集（个帮派），编号为。第i个点集代表第i个帮派占据的点的集合。定义一个节点被占领当且仅当满足下面其中一个条件： 该结点被一个帮派所占据。 该结点位于被占领的两个结点的路径上。 Q个询问，每个询问给出一个点，一个数，和个数（），代表在这个询问中选取（）这个帮派，
展开全文
题目链接 题意：题解： AC代码 /*
Author : zzugzx
Lang : C++
Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#d
展开全文
问题描述 树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。 当一些帮派结成联盟时，他们会
展开全文
前言: 这个每日一题对我来说稍微复杂了亿点点... 思路: 首先的题目的条件就是所有点的lca到所有点的路径都被标记了.我们要求点V到这些点集的一个最小距离. 假如这个点集的LCA和V的lca不是LCA的话,那么显然的一个结论距离就是V到lca的距离. 假如不是,那么V一定位于LCA的子树中.这是我
展开全文
题目描述 树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。当一些帮派结成联盟时，他们会
展开全文
题意简化： 首先给出一棵树，其次询问一个点集，求包含这个点集的最小生成树与询问点x的最短距离 题目思路 首先考虑，如何确定这个点集的最小生成树：首先跑一个LCA，找出所有点公共的LCA，那么这个最小生成树的点集根节点(也就可以确定了) 之后就可以考虑这两种情况： 1.如果询问点，不在这个子树内
展开全文
题目：有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。有k个帮派，每个帮派占领ci个城市。帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？ 思路：在树
展开全文
这题太变态了吧。 分析 我们预处理出每个帮派的lca节点，当帮派合并的时候，我们就可以求各个帮派的lca的节点。 假设首都节点是u,各个帮派的lca是pos，分两种情况 当lca(u,pos) ！= pos的时候，说明u不在pos的子树下，答案就是dis(u,pos)。 当lca(u,pos)
展开全文
NC13950 Alliances 题目地址： https://ac.nowcoder.com/acm/problem/13950 基本思路： 我们先对题进行分析，如果不考虑联盟，只对单一的帮派来说，我们找距离首都最近的一个帮派。那么分情况讨论一下，如果首都不在这个帮派的的子树里，那么最短距
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
