树上差分之点差分
给定一棵树,给出若干次修改操作以及少次查询操作
修改操作:给定两个点$u,v$,将$u,v$路径上所有的点权值$+k$
查询操作:询问点$x$的权值
思路:树上差分,要修改$u,v$路径上的所有点,只需
$f[u]+=k$
$f[v]+=k$
$f[lca(u,v)]-=k$
$f[father[lca(u,v)]]-=k$
点$x$的权值就是以$x$为根的子树的权值和(前缀和)。
由于查询的时候需要跑一边dfs,因此查询次数不能过多
AC代码:
1 | struct node |