SP10628 COT – Count on a tree

主席树的综合运用题. 前置芝士 可持久化线段树:其实就是主席树了. LCA:最近公共祖先,本题需要在log⁡2N\log_2Nlog2​N及以内的时间复杂度内解决这个问题. 具体做法 主席树维护每个点到根节点这一条链上不同树出现的次数,然后发现这个东西是可以相减的,于是这条链上每个数出现的次数就变成了sum[u]+sum[v]−2∗sum[LCA(u,v)]sum[u]+sum[v]-2*sum[LCA(u,v)]sum[u]+sum[v]−2∗sum[LCA(u,v)].然后就可以发现这个是错的,如果按这个式子计算最后的链上就没有LCA位置的值了,所以在范围包含val[LCA(u,v)]va