蓝桥杯2023年第十四届省赛真题-砍树 LCA+树上差分
摘要：解题思路:我们先把ai和bi之间的路进行差分处理，然后遍历还原，最后对几条边进行遍历，如果它被m条路径覆盖了，则统计，没有任何满……
砍树(详细注释)--先暴力--再树链剖分+树差分优化
解题思路:满足条件的边一定是每组数据都要经过的公共边例如：36；45；那满足条件的边一定既是3到6的路径又是4到5的路径，那这条边权值一定为m；再选出最大编号的边注意事项:参考代码:暴力(只能过一部分)：#includeusingnamespacestd;typedefpairpii;constint
蓝桥杯2023年第十四届省赛真题-砍树（树上差分）
#解题思路对于每一对$$(a_i,b_i)$$，$$a_i$$到$$b_i$$之间的边都可以砍掉；把可以砍掉的边权值+1，那么这条边的权值$$w$$表示砍掉这条边可以满足$$w$$对$$(a_i,b_i)$$不连通;最后找到权值等于$$m$$且编号最大的删去即可，
tarjan + lca + 树上差分
#思路*主要讲讲怎么在边上树上差分吧具体的思路就是，将要查询`diff[u]+=1,diff[v]+=1,diff[lca]-=2`,然后*状态一*状态二![](/image_edit