Luogu3128 [USACO15DEC]最大流Max Flow 树上差分 图论 数据结构

Luogu3128 [USACO15DEC]最大流Max Flow 树上差分

此题不是网络流! 树上差分裸题,将差分思想用在树上。要对整条路径上的点进行操作,可以先考虑对路径的两个端点、LCA以及LCA的父节点进行操作,最后一遍DFS,更新各节点信息。例如在本题中,要将整条路径的点权加1,可以给两个端点分别加1,给LCA减1,再给LCA的父节点减1。完成所有操作后,只需要DF···