2022.11.29 vjudge构造、思路题

Weighting a Tree

构造切入点：

调整

总结：

1. 图上的题，可以先考虑树上的做法。（尤其是构造题）
2. 首先我们要知道这种“点与跟他连着的所有边的关系”什么的题的套路就是找生成树。---ywy_c_asm
3. 先对生成树构造完之后，通过基环来调整根的答案。
4. 这种题，可以先求出图的生成树，然后让除了树根以外的点都满足条件。最后通过非树边，调整树根，让树根满足条件。

Restoring Map

构造切入点：

找性质

总结：

1. 看到距离某个点 \(\leq 2\) 应该想到从叶子节点的角度思考问题
2. 两个非叶子节点 \((x, y)\) 之间存在边，当且仅当存在两个集合的交为 \(\{x, y\}\) . （集合定义为和这个点距离 \(<2\) 的点所构成的集合）

Largest Smallest Cyclic Shift

构造切入点：

合并，调整。

总结：

1. 这题怎么说呢，看完题解发现是很简单的一道贪心，但就是想不到。
2. 这题的关键点在于构造的方式和构造的切入点。如果想直接构造出来，或者不断往后加字符，那么会非常难，正确的构造方式应该是先通过不断合并字符串的方式来构造，而这个方法正好很难想到。

Adding Edges

很毒瘤的构造题。不知道为什么只有铜牌题难度。

Parquet Re-laying

构造切入点：

调整，递归构造。

总结:

总结不出来