Atcoder abc337

發表於 更新於 分類於 ， Disqus： 文章字數： 886 所需閱讀時間 ≈ 3 分鐘
G(换根dp)

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
2
3
4
5
6
     u
v1,v2,v3,...

u
|edge
v1

若和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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using ll=long long;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
int read(){int r;scanf("%d",&r);return r;}
int main() {
  int N=read();
  vector<vector<int>> g(N);
  rep(i,1,N){
    int u=read()-1;
    int v=read()-1;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<ll> imos(N); // 树上前缀和
  atcoder::fenwick_tree<ll> fw(N);
  // O(N log N) time
  [dfs{[&](const auto &f, int u, int fa) -> void {
    auto lu_in{fw.sum(0, u)}; // 进入时 < u 的, less than u
    auto lfa_in{fw.sum(0, fa)}; // 进入时 < fa 的,less than fa
    fw.add(u, 1); // fw[u] += 1
    for (const auto v : g[u]) if (v != fa) f(f, v, u); // Recursion
    auto lu_out{fw.sum(0, u)}; // 离开时 < u的
    auto lfa_out{fw.sum(0, fa)}; // 离开时 < fa的

    auto lu_inc{u - (lu_out-lu_in)}; // 上面的差值 就是子树中<u的, 这里的增量是子树外的, 因为0-index不需要再减1
    auto lfa_inc{lfa_out - lfa_in}; // 上面的差值 就是子树中<fa的

    imos[0] += lfa_inc; // 全局增加
    imos[u] += lu_inc - lfa_inc; // 子树u 上的增量, 后面用树上前缀和即可
  }}] {
    dfs(dfs, 0, 0);
  }();
  // 完成树上前缀和
  [dfs{[&](const auto &f, int u, int fa, ll inc) -> void {
    imos[u]+=inc;
    for (const auto v : g[u]) if (v != fa) f(f, v, u, imos[u]);
  }}] {
    dfs(dfs, 0, 0, 0);
  }();

  for (const auto ans : imos) printf("%lld ",ans);
  return 0;
}

总结

整体是换根dp+fenwick维护想到了， 问题在于子树中比给定值小的怎么计算

这里 就是进入和出来的 值的差值就够了！！！！，我怎么这也没自己想到