给出一棵树,给定每一个点的 access 次数,计算轻重链切换次数的最大值,带修改.
假设 u 的子树发生了两次 access ,那么当且仅当这两次 access 的点来自 u 的两个不同的儿子的子树,答案才会 +1
要使得答案最大,就是尽量让所有相邻发生的 access 都来自不同子树
把同类型的数挪到一边就是当 \(2\times h\ge t+1\) 时,答案是 \(2(t-h)\) ,否则是 \(t-1\)
令$ f_i$表示 \(i\) 的子树 access 的总次数,如果 \(2f_i\ge f_{fa_i}+1\) 那么连实边 \((i,fa_i)\) 其他的都是虚边
因为 \(2(f_i+w)\ge(f_{fa_i}+w)+1\)所以实边还是实边,并且答案不会变化 \((\Delta=2[(f_{fa_i}+w)-(f_i+w)]-2(f_{fa_i}-f_i)=0)\)
所以我们只需要找到路径上的虚边进行修改就好了
原文：https://www.cnblogs.com/lizehon/p/10519171.html