Atcoder abc337
https://atcoder.jp/contests/abc337
G - Tree Inversion
n点树
for u = 1..n
求 有多少(v,w),满足 w在u..v路径上(w可以等于u,v),且v < w
n 2e5
1024mb
我的思路
如果是一个点u,
那么可以把u作为根,做dfs
dfs过程中 维护父向点集,和求 >= 当前点的个数
这样可以 树状数组维护,是O(n log n) 可以做的
但这同时求多个似乎不太好转换
1 | u |
若和u直接相连的点是v1,v2,…,v3
从换根dp的角度想
如果u换成v1,把这条边叫做edge,那么原来 (u-v2子树),(u-v3子树)… 的贡献都不会变
只有w=u,而v 在(u-v1子树)中的贡献不见了
ans -= tree(edge-v1子树, < u)
多出来的是w=v1,而v在 u-v2/v3/…
ans += tree(edge-u, < v1)
所以如果有预计算 每条边 u0-u1,
tree(u0,< u1) 和tree(u1,< u0),就可以实现换根dp
这怎么算呢,
想的是 启发式合并,每次点少的向多的合并
同样fenwick维护,似乎能做?
题解
考虑(v < w)会对哪些u产生贡献
也就是移除w后u,v在不同连通块里
任意固定一个根
那么 u所在的位置 要么是 一个子树,要么是 所有点 减去 一个子树
固定一个 顶点p的子树,如果w=p,其v不在 子树中,那么(w,v)会对子树所有点产生贡献
次数x = w-1-(子树中比w小的数的个数)
固定一个 顶点p的子树,如果w是p的父节点,v在子树中,那么会对子树外的所有节点产生贡献
次数x = (子树中比w小的数的个数)
而这种做一个反向操作就是,所有贡献tot+=x,然后子树减少x
tot=for edge[u上v下] sum(count(子树v, < u))
for edge[u上v下], add[v子树] = w-1-count(子树v,< v) - count(子树v,< u)
这里题解的内容和我上面按照 边两端来看是一样的
然后就是fenwick维护
代码
https://atcoder.jp/contests/abc337/submissions/50119240
1 |
|
总结
整体是换根dp+fenwick维护想到了, 问题在于子树中比给定值小的怎么计算
这里 就是进入和出来的 值的差值就够了!!!!,我怎么这也没自己想到