建立机制_建筑人才网筑才网_谷歌广告联盟怎么做_自己怎么免费做网站

本文涉及知识点

C++贪心
C++BFS算法

「DTOI-4」行走

题目背景

小 L 感到无聊，于是希望在树上行走。

题目描述

小 L 有一棵 $n$ 个点的树，树上点有点权，其中第 $i$ 个点权值为 $a_i$ 。

他不喜欢奇奇怪怪的权值，于是他保证 $a_i$ 一定是 $- 1, 0, 1$ 之一。

他认为在树上行走是有趣的，于是他想要在这棵树上走出一条路径 $P$ ，其需要满足以下条件：

$P$ 是一条可以为空的简单有向路径。
设 $P$ 中依次经过的点为 $P_1, P_2, \cdots, P_{|P|}$ ，则你求出的 $P$ 需要满足 $P_1 = 1$ 。
设 $\displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$ ，则你求出的 $P$ 需要满足 $f (P)$ 最大。
在 $f (P)$ 最大的前提下，你求出的 $P$ 还需要满足 $P$ 的字典序最小。

请你求出符合上述条件的路径 $P$ 。

关于本题中字典序的定义：

设有两条待比较的路径 $\neq Q$ 。

若存在 $\leq i \leq \min(|P|, |Q|)$ ，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i < Q_i$ ，则我们称 $P$ 的字典序小于 $Q$ 。
若存在 $\leq i \leq \min(|P|, |Q|)$ ，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i > Q_i$ ，则我们称 $P$ 的字典序大于 $Q$ 。
若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $∣ P ∣ < ∣ Q ∣$ ，则我们称 $P$ 的字典序小于 $Q$ 。
若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $∣ P ∣ > ∣ Q ∣$ ，则我们称 $P$ 的字典序大于 $Q$ 。

输入格式

第一行，一个整数 $n$ ；

第二行， $n$ 个整数 $a_1, a_2, \cdots, a_n$ ；

接下来 $n - 1$ 行，每行两个整数 $u, v$ ，表示树上的一条边。

输出格式

一行， $∣ P ∣$ 个整数，表示你求出的路径 $P$ 中依次经过的点。

特别的，若 $P$ 为空路径，请不要进行任何输出操作。

样例 #1

样例输入 #1

5
1 0 -1 1 -1
1 2
2 3
2 4
1 5

样例输出 #1

1 2 4

提示

样例 #1 解释

$P = [1, 2, 4]$ 时 $\frac{1}{4} = \frac{5}{4}$ 。可以证明不存在更优的 $P$ 。

数据范围

$\textbf{Subtask}$	$n$	$a_i$	依赖	分值
$1$	$\leq n \leq 50$	无特殊限制	无	$\operatorname{pts}$
$2$	$\leq n \leq 500$	同上	$1$	$\operatorname{pts}$
$3$	$\leq n \leq 5 \times 10^3$	同上	$1, 2$	$\operatorname{pts}$
$4$	$\leq n \leq 10^5$	同上	$\sim 3$	$\operatorname{pts}$
$5$	无特殊限制	$a_i \in \{-1, 1\}$	无	$\operatorname{pts}$
$6$	同上	无特殊限制	$\sim 5$	$\operatorname{pts}$

对于 $100\%$ 的数据， $\leq n \leq 5 \times 10^5$ ， $a_i \in \{-1, 0, 1\}$ ， $\leq u, v \leq n$ ，保证给出的边可以构成一棵无根树。

贪心

性质一：路径一定不包括权值为-1的节点，就算后面全部是1，也补不过来。增加临接表的时候，忽略相关边。
如果节点1权值为-1，直接返回0。
性质二：如果存在为1的子节点，则忽略所有为0的子节点。

不考虑字典序,BFS

leves[i]记录第i层的节点，如果此层包括权值为1的节点，则删除所有权值为0的节点。
leves.back()[0]就是答案。
特例：一个字符串是另外一个字符串的前缀。如果是小于，比如10和 1001，合法。如果是相等，如：10 1000,则不合法。假定最后有i1个0。则结果是：leves[leves.size()-1-i1][0]，全0要特殊处理。

考虑字典序

临接点按字典序排列。BFS的时候，记录字父节点，方便逆推路径。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>#include <bitset>
using namespace std;template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {vector<T> ret(n);for(int i=0;i<n;i++) {scanf(pFormat, &ret[i]);	}return ret;
}template<class T = int>
vector<T> Read( const char* pFormat = "%d") {int n;scanf("%d", &n);vector<T> ret;T d;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}string ReadChar(int n) {string str;char ch;while (n--) {do{scanf("%c", &ch);} while (('\n' == ch));str += ch;}return str;
}class CNeiBo
{
public:static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};
class Solution {
public:vector<int> Ans(vector<int>& a, vector<vector<int>>& edge){const int N = a.size();auto neiBo = CNeiBo::Two(N, edge, false, 1);for (auto& v : neiBo) {sort(v.begin(), v.end());}vector<int> par(N, -2);vector<vector<int>> leves;vector<int> leve1, leve0;auto Add = [&](int cur, int iPar) {if (-2 != par[cur]) { return; }par[cur] = iPar;if (0 == a[cur]) { leve0.emplace_back(cur); }if (1 == a[cur]) { leve1.emplace_back(cur); }};Add(0, -1);while (leve0.size() || leve1.size()) {auto curs = leve1.size() ? leve1 : leve0;leves.emplace_back(curs);leve0.clear();leve1.clear();for (const auto& cur : curs){for (const auto& next : neiBo[cur]) {Add(next, cur);}}}while (leves.size() && (0 == a[leves.back()[0]])) {leves.pop_back();}if (leves.empty()) { return {}; }vector<int> ans;int cur = leves.back()[0];while (-1 != cur) {ans.emplace_back(cur + 1);cur = par[cur];}return vector<int>(ans.rbegin(), ans.rend());}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint n;scanf("%d", &n);auto a = Read<int>(n);vector<vector<int>> edge(n - 1);for (int i = 0; i+1 < n; i++) {edge[i] = Read<int>(2);}auto res = Solution().Ans(a,edge);for (auto i : res){cout << i << " ";}#ifdef _DEBUG//Out(a, "a=");//Out(edge, ",edge=");
#endif	return 0;
}

单元测试

vector<int> a;vector<vector<int>> edge;TEST_METHOD(TestMethod1){a = { 1 }, edge = {};auto res = Solution().Ans(a, edge);AssertEx({ 1 }, res);}TEST_METHOD(TestMethod2){a = { 0 }, edge = {};auto res = Solution().Ans(a, edge);AssertEx({  }, res);}TEST_METHOD(TestMethod3){a = { -1 }, edge = {};auto res = Solution().Ans(a, edge);AssertEx({  }, res);}TEST_METHOD(TestMethod4){a = { 1,0 }, edge = { {1,2} };auto res = Solution().Ans(a, edge);AssertEx({ 1 }, res);}TEST_METHOD(TestMethod5){a = { 1,0,0,0 }, edge = { {1,3},{1,2},{3,4} };auto res = Solution().Ans(a, edge);AssertEx({ 1 }, res);}TEST_METHOD(TestMethod6){a = { 1,1,1,0 }, edge = { {1,3},{1,2},{3,4} };auto res = Solution().Ans(a, edge);AssertEx({ 1,2 }, res);}TEST_METHOD(TestMethod7){a = { 1,0,0,1 }, edge = { {1,2},{1,3},{3,4} };auto res = Solution().Ans(a, edge);AssertEx({ 1,3,4 }, res);}TEST_METHOD(TestMethod11){a = { 1,0,-1,1,-1 }, edge = { {1,2},{2,3},{2,4},{1,5} };auto res = Solution().Ans(a, edge);AssertEx({ 1,2,4 }, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。