树上差分

xiaoxiao2021-02-28  112

树上差分

Max Flow NKOJ3605

给定一棵有N个点的树,所有节点的权值初始时都为0。 有K次操作,每次指定两个点s,t,将s到t路径上所有点的权值都+1。 请输出K次操作完毕后权值最大的那个点的权值。 2≤N≤50,000 1≤K≤100,000

对于每一次修改s,t,将s,t的权+1; 将LCA(s,t)和father[LCA(s,t)]的权-1; 一个点最终被覆盖的次数就是这个点所在子树的权和。

对于每一次修改s,t,将s,t的权+1; 将LCA(s,t)和father[LCA(s,t)]的权-1; 一个点最终被覆盖的次数就是这个点所在子树的权和。

转载请注明原文地址: https://www.6miu.com/read-61744.html

最新回复(0)