D. Edge Split
算法本质
思维
思路推演
找规律，要从小规律开找，然后推广。
自己拿张纸，任意画个小图，然后其中的边变化颜色：比如全涂红、随机涂等等。
就会发现了规律：涂边时，相同颜色边不成环收益 > 成环收益。
多试几个图，再根据这个规律总结数学公式，会发现果真如此。
题目表示，边数m最多为n+2。所以选择首先先弄一棵树出来，数全为红色，剩下的为蓝色。
现在唯一需要担心的是，蓝色部分最多有3条边，可能构成环，那得替换一条边，那应该怎么样替换才能使得替换后大家都没有环呢？
又拿出一张纸，开始画图，自己动手……
然后发现，替换任意一蓝边都是可行的。随机找一条边，设其中的两个点为u v，红边的选择必须是u v到其最近公共组先的路径上的边。
因为这题的性质，特别是只找路径中一个边即可，所以并不用搞一套最近公共组先模板，设u v两点其中深度更大的点是v，那红边设定位v--fu[v]即可。
注意，因为最后的输出结构，所以需要记录所有边的下标。
代码思路
建树，同时维护dep[]、fu[]
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。题目
算法本质
思路推演
代码思路
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。题目
算法本质
思路推演
代码思路
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。题目
算法本质
思路推演
代码思路
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)