题目传送门 题解 题目理解与强调 题目给出的是一个$n$个点$n$条边的无向连通图，$n$个点$n$条边可以看出这是一个基环树，树上每个点都有两种权值，分别表示美观度和长度，我们从一个点出发的时候，要找美观度最大的一条边走，如果那个点已经被走过了，就不走了，换向另一条边，过程类似于DFS。 思路分析 既然是在一棵基环树上遍历每个点，走过这$n$个点…

在一个图中进行DP，对于部分题目来说随意一个顺序会破坏DP的无后效性原则，例如题目”洛谷：P3387 【模板】缩点“中，需要找出DAG中的一条路径，且这条路径上的点权和最大。我们需要从枚举的第一个点开始，记录$ dp[i] $，表示从第一个点到当前节点的最大点权和，每次向下枚举一个点，都需要保证我们要枚举的这个点的入度为$0$，即保证它不会再被其他…