小美和小团所在的城市包含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; }

编辑于 2023-07-30 19:34:56

以上就是关于问题小美和小团所在的城市包含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链游项目方科学家脚本开发培训