小美和小团所在的城市包含N 个乡镇，乡镇被编号为1 到N 并按中心化管理，N 个乡镇按层级构成树型关系：即以1 号乡镇为中心( 根) ，对于2 号到N 号乡镇，i 号乡镇的上级乡镇为A[i] 号乡镇（1<=A[i]<i ），或者说i 号乡镇是A[i] 号乡镇的一个下属乡镇。每个乡镇只有一个上级乡镇（除了1 号乡镇没有上级乡镇）和若干个下属乡镇。 该城市由2(N-1) 条单向道路连接各乡镇。除了1 号乡镇，每个乡镇都有一条长为1 的高速公路通向其上级乡镇，而其上级乡镇则有一条长为2 的普通公路通向该乡镇。 现在，小美和小团打算在该城市开展外卖业务。若他们在某个乡镇设立站点，则从该乡镇出发距离不超过2 的乡镇都可以享受到他们的外卖服务。那么，他们想知道至少要在多少个乡镇设立站点，才能使所有乡镇都享受到外卖服务。
区块链毕设网qklbishe.com为您提供问题的解答
小美和小团所在的城市包含N个乡镇，乡镇被编号为1到N并按中心化管理，N个乡镇按层级构成树型关系：即以1号乡镇为中心(根)，对于2号到N号乡镇，i号乡镇的上级乡镇为A[i]号乡镇（1<=A[i]<i），或者说i号乡镇是A[i]号乡镇的一个下属乡镇。每个乡镇只有一个上级乡镇（除了1号乡镇没有上级乡镇）和若干个下属乡镇。
该城市由2(N-1)条单向道路连接各乡镇。除了1号乡镇，每个乡镇都有一条长为1的高速公路通向其上级乡镇，而其上级乡镇则有一条长为2的普通公路通向该乡镇。
现在，小美和小团打算在该城市开展外卖业务。若他们在某个乡镇设立站点，则从该乡镇出发距离不超过2的乡镇都可以享受到他们的外卖服务。那么，他们想知道至少要在多少个乡镇设立站点，才能使所有乡镇都享受到外卖服务。
-
这道题目可以看成对树上的节点进行染色, 一个节点染色, 那么其父节点和祖父节点都会被染色, 孩子节点也会被染色, 求最少多少个节点, 可以让整个树都染上色
-
考虑示例 1 (`1 1 3 3`) 中的输入, `4` 和 `5` 节点不应该被染色, 而应该染色 `3` 节点。换言之, 如果对节点 `a` 进行染色, 其能对 `a` 的子树的染色范围仅为 `a` 本身, 那么一定可以对 `a` 的父节点 `b` 进行染色, 从而尽可能减少染色次数。也就是说, 我们要尽可能推迟染色
-
因此, 我们拓扑排序, 由外向内遍历, 尽可能把染色往内部推迟
-
每遍历到节点 `n`, 如果 (1) 其存在一个子节点没有被染色 或者 (2) 其本身尚未有颜色, 且不能向内推迟, 那么我们染色
struct Node { int parent; vector<int> sons; }; static constexpr int NO = 0, LIGHTED = 1; int main(int argc, char const* argv[]) { std::ios::sync_with_stdio(false); auto T = 0; cin >> T; while (T--) { auto M = 0; cin >> M; vector<Node> nodes(M + 1); for (auto i = 2; i <= M; i++) { auto& snode = nodes[i]; auto p = 0; cin >> p; auto& pnode = nodes[p]; pnode.sons.push_back(i); snode.parent = p; } if (M == 1) { cout << 1 << std::endl; continue; } // 首先找到所有的叶子节点 vector<int> inds(M + 1, 0); vector<int> colors(M + 1, 0); std::queue<int> q, nq; for (auto i = 1; i <= M; i++) { auto const& node = nodes[i]; inds[i] = static_cast<int>(node.sons.size()); if (inds[i] == 0) { q.push(i); } } auto ans = 0; while (!q.empty()) { while (!q.empty()) { auto const& nid = q.front(); q.pop(); auto const& node = nodes[nid]; // 判断当前节点是否要上色 auto need = 0; if (colors[nid] == NO) { if (node.parent >= 1) { need = 2; } else { need = 1; } } else { // 如果有一个孩子没有 color auto const& nodesons = node.sons; for (auto const& s : nodesons) { if (colors[s] == NO) { need = 1; break; } } } if (need == 1) { // 需要上色, 那么先上色 ans++; // 自己 colors[nid] = LIGHTED; // 所有父亲 if (node.parent >= 1) { colors[node.parent] = LIGHTED; auto const& parentnode = nodes[node.parent]; if (parentnode.parent >= 1) { colors[parentnode.parent] = LIGHTED; } } // 孩子不上色 } else if (need == 2) { // 依赖父亲上色 colors[node.parent] = LIGHTED; } // 做完, pop if (node.parent >= 1) { inds[node.parent]--; if (inds[node.parent] == 0) { nq.push(node.parent); } } } q.swap(nq); } cout << ans << std::endl; } return 0; }
以上就是关于问题小美和小团所在的城市包含N 个乡镇，乡镇被编号为1 到N 并按中心化管理，N 个乡镇按层级构成树型关系：即以1 号乡镇为中心( 根) ，对于2 号到N 号乡镇，i 号乡镇的上级乡镇为A[i] 号乡镇（1<=A[i]<i ），或者说i 号乡镇是A[i] 号乡镇的一个下属乡镇。每个乡镇只有一个上级乡镇（除了1 号乡镇没有上级乡镇）和若干个下属乡镇。 该城市由2(N-1) 条单向道路连接各乡镇。除了1 号乡镇，每个乡镇都有一条长为1 的高速公路通向其上级乡镇，而其上级乡镇则有一条长为2 的普通公路通向该乡镇。 现在，小美和小团打算在该城市开展外卖业务。若他们在某个乡镇设立站点，则从该乡镇出发距离不超过2 的乡镇都可以享受到他们的外卖服务。那么，他们想知道至少要在多少个乡镇设立站点，才能使所有乡镇都享受到外卖服务。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
