Atcoder abc269

發表於 2022-10-16 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 2.6k 所需閱讀時間 ≈ 9 分鐘

G(DP)Ex(重链轻链,DP,分治,fft,HLD)

https://atcoder.jp/contests/abc269/tasks

G - Reversible Cards 2

给定n张卡, 每张正面ai,反面bi

初始都正面

问对于 k=0..m 的每个取值

让可见面=k的最小翻转次数

所有 ai+bi 和为m, 所有ai,bi 在[0,m] 之间的整数

范围

n 2e5

m 2e5

1024mb

我的思路

先想的是分治

f[i..j][v] 表示[i..j] 这一段可见面=v的最小翻转次数

f[i..j][v] = min(f[i..mid][x]+f[mid+1..j][v-x])

似乎需要min卷积并不会

想过网络流, 但这里没有最大最小什么的, 唯一的最小就是最小次数, 但感觉网络流上去等于k 看起来更像是费用和,

预处理, 先计算所有Ai的和, 然后翻转看成 Bi-Ai 的增量

问题变成有n个变量, 问和 = k-sum(A) 的最小选择个数

一股 spfa的感觉?

不会

题解

一样的想法, 堪称增量

然后先做个显然的滚动dp

dp = [inf] * (M+1)

dp[sumA] = 0

if(i-c in [0,m]) dp[i] = min(dp[i],dp[i-c]+1);

这个明显O(nm) 会 TLE

令Ci=Bi-Ai

考虑C的性质

显然 sum(|C|) = sum(|Bi-Ai|) <= sum(|Bi|+|Ai|) <= M

因此 C中, 不同的值至多 O(sqrt(M))个!!!!!!!!!!

然后同样的Ci统计出现次数, 用跳点+滑窗随便搞了

代码

https://atcoder.jp/contests/abc269/submissions/35793184

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}

int main(){
  int n = read();
  int m = read();
  int s_a = 0;
  map<int,int> F; // diff, count
  rep(i,0,n){
    int a=read();
    int b=read();
    s_a+=a;
    F[b-a]++;
  }
  const int INF = 0x3f3f3f3f;
  vector<int> dp(m+1,INF);
  dp[s_a] = 0;
  for(auto [d,c]:F) if(d!=0){ // O(sqrt m) 个
    int x = 1; // binary 逼近c !!
    while(c){
      int s = min(x, c);
      if(d > 0){ // 注意滚动顺序
        per(i,0,m-d*s+1) dp[i+d*s] = min(dp[i+d*s], dp[i]+s);
      } else {
        rep(i,-d*s,m+1)  dp[i+d*s] = min(dp[i+d*s], dp[i]+s);
      }
      c -= s;
      x *= 2;
    }
  }
  rep(i,0,m+1) printf("%d\n",dp[i] <= n?dp[i]:-1);
  return 0;
}

Ex - Antichain

给定n个点, 根为1的树,每个点的父节点编号小于它

一个非空点集S 满足两两没有祖先关系则认为是好的

对于k=1..n 问有多少个点数为k的集合是好的, 个数 mod 998244353

范围

n 2e5

1024mb

我的思路

一个节点被选, 意味着子节点全部不选,

暴力思路就是 dp[u][c] = 以u为根的子树选了c个节点满足要求的方案数

dp[u][1]+= 1 选根

dp[u][x]+= sum dp[v0][x0] * dp[v1][x1] * ...,vi 是u的直接子节点, sum(xi) = x 不选根

听起来就是 dp[v0], dp[v1] ... 的卷积得到 dp[u]

生成方程就是

f[leaf] = 1+x

f[u] = x + f[v0] f[v1] …

dsu + fft on tree ????

题解

Heavy-Light Decomposition (HLD) 是一个把有根树切分成多个链的方案, 下面用的不是HLD, 是Centroid Path Decomposition

树(N点,根1)

首先预计算所有子树的节点个数

把点u的其中一条最大的子树节点v连出的边叫做重边, 其余u连出到子节点的叫做轻边

红重,蓝轻

重轻树

性质:

任何叶子到根的路径可以被切分成 $O(\log n)$ 个重path(路径), 和轻edges(边)

轻边个数: 反证法,从下向上, 因为 u->v 若是轻边那么u子树大小大于 2倍v的子树大小, 如果大于$\log(n)$, 则总的大于n

重轻相互间隔, 所以重path 也是 $O(log n)$

因此任意两个节点之间, 也是$O(\log n)$ 条重path

~~因此如果预处理了, 那么任意两点之间的操作就是$O(\log N)$条边~~

使用前序来实现:

首先 dfs 计算子树大小, 和指定重链(把重儿子swap 到儿子的第一个)
计算每个点所在的重链向根方向的头部, 记录在head 中

int order[N_MAX + 3]; // 前序遍历 的 index
int head[N_MAX + 3];  // head[i] = 包含i 的向根方向的重path的头部
void dfs2(int u/*节点*/, int &i /*前序遍历index*/) {
  order[u] = i++;
  for(auto& v/*u的子节点*/ : g[u]) {
    head[v] = (g[u][0] == v ? head[u] : v);
    dfs2(v, i);
  }
}

性质: 任何重path, 是前序遍历的连续一段(基于上面的重儿子swap), 考虑从重链根开始的dfs 显然

这样考虑的话, 可以计算每个点到它重链根的贡献,(例如用segtree管理区间), 这样对于任何

HLD类似的其它应用例如 Weighted-Union Heuristic

回到这个问题

首先可以树上DP+fft 可以$O(n^2)$

也是用生成方程给你表示 $f_u(x)$ 表示根$u$的子树每个节点

考虑子问题, $N$点根$1$的树, 1-2-3-…-M 是树上路径, 需要计算$i \in (M,N]$ 的$f_i(x)$

令$g_u(x) = \prod f_v(x)$, $v$的父节点是$u$, 且$v > M$, 也就是点$u$的大于$M$的子节点选取后的方案数,

有

$f_1(x) = \sum_{i=1}^{M+1}\left( (\text{1 if }i = M+1\text{ else }x) \prod_{j=1}^{i-1} g_j(x) \right).$

意义是例如:

i	意思	贡献
1	选1	$x * 1$
2	选2, 1不选	$x * g_1(x)$
3	选3, 1,2不选	$x * g_1(x) * g_2(x)$
M	选M , 1…M-1 不选	$x * g_1(x) * \cdots * g_{m-1}(x)$
M+1	1到M都不选	$g_1(x) * \cdots * g_{m}(x)$

按照上面这样算的话, 把数字1-M变成从1开始的一条重path 就可以把上面的计算所有$> M$的改成所有轻链, 修改以后的

$g_u(x) = \prod_{v \neq \text{heavy}_u} f_v(x).$ , 其中v的父节点是u, 且v不是重节点

$f_u(x) =$ 重path上, 的有序的数组 $h_u = (g_u,g_{v_0},g_{v_1},\cdots)$

dp时候,直接维护$h_u$, 在未达到重path的根时不要算$f_u$的具体值, 先维护数组

叶子, $h_u = (1)$
重儿子, 相当于 $h_u = [g_u, …h_{\mathrm{heavy}u}]$ ,即$h{\mathrm{heavy}_u}$头部塞入$g_u$

复杂度估计

$h_u$ 到计算出 $f_u$ 的复杂度
$g_u$ 的计算复杂度

$h_u$ 到计算出$f_u$ 的复杂度

为$O(S_u \log^3 (S_u))$, 其中$S_u$是$u$的子树的节点个数

其实就是给g的序列, 求下面这个

x
x g1
x g1 g2
x g1 g2 g3
x g1 g2 g3 g4
...
  g1 g2 g3 ... gn

先不管$x$的部分

那么令 func([i..j]) 返回 $[S = [i..j-1]的结果,P=\prod g_i \cdots g_j]$

左半 Left part
g1
g1 g2
...
g1 ... gm
右半 
g1 ... gm+1
...
g1............gn

有 $[S,P] = [S_L + P_L * S_R, P_L * P_R]$, 所以如此分治,最后处理$x$倍数

我们只需要对所有轻儿子和点1 做$h_u \to f_u$的计算

$\sum S_{轻儿子} = O(N \log N)$

证明, 既然是$\sum S_{轻儿子}$, 换过来从统计的角度看, 每个点,到根的路径上, 每有一条轻边, 就会在 $S_{轻儿子}$中贡献$1$, 又因为上面有性质每条从根向下的path中轻儿子个数$O(log N)$, 所以显然$sum S_轻儿子 = O(N log N)$

综合一下总的 $h\to f$的计算代价也是 N log^3 N 级别的

代码

https://atcoder.jp/contests/abc269/submissions/35807621

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
using mint = atcoder::modint998244353;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;}
using poly = vector<mint>;
poly operator*(const poly& a, const poly& b) { return atcoder::convolution(a, b); }
poly operator+(const poly& a, const poly& b) {
  poly c{a};
  if (a.size() < b.size()) c.resize(b.size());
  rep(i,0,b.size()) c[i] += b[i];
  return c;
}

int P[200010]; // P[u]=u的父节点
vector<int> child[200010]; // child[u] = u的子节点, child[u][0]为重儿子
poly f(int);

poly g(int u){
  vector<poly> a={poly{1}};
  rep(i,1,child[u].size()) a.push_back(f(child[u][i])); // 轻边f
  while((int)a.size() >= 2) { // 分治计算
    vector<poly> b;
    rep(i,0,a.size()/2) b.push_back(a[i*2] * a[i*2+1]);
    if (a.size() & 1) b.push_back(a.back());
    a=b;
  }
  return a.back();
}

vector<poly> heavy(int u) { // 返回的 h = 倒着的g数组, 从u向下的重path
  if (child[u].empty()) return {poly{1}}; // leaf
  vector<poly> res = heavy(child[u][0]); // 重儿子 std::move
  res.push_back(g(u)); // 倒着放的
  return res;
}

// [l,r) 这里 的h是倒着从下向上放的, 所以SR+SL*PR, 如果是正着放就是 SL+PL*SR
pair<poly,poly> dc(vector<poly>& h, int l, int r) { // 返回 l..r 构成三角形, {l..r-1的和, 第r行l..r的prod}
  if (l+1 == r) return {poly{1}, h[l]};
  int m = (l+r)/2;
  auto [SL,PL] = dc(h, l, m);
  auto [SR,PR] = dc(h, m, r);
  return {SL*PR+SR, PL*PR};
};

poly f(int u) { // 返回的 f_u()
  auto h = heavy(u);
  auto [S, P] = dc(h, 0, h.size());
  return S * poly{0, 1} + P; // x * 除了最后一行的和 + 最后一行
}

int main() {
  int n=read();
  rep(i,2,n+1)P[i]=read(); // 父节点
  vector<int>sub(n+1,1); // sub[u]=以u为根的子树的节点数
  per(i,1,n+1){
    sub[P[i]] += sub[i]; // 计算子树大小
    child[P[i]].push_back(i);
    for (auto& j : child[i]) if (sub[j]>sub[child[i][0]]) swap(j, child[i][0]); // 指定重儿子
  }
  auto ans = f(1);
  ans.resize(n+1); // 可能不足n
  rep(i,1,n+1)printf("%d\n",ans[i].val());
}

总结

DP 优化分析完全不会

其实这里值和绝对值不超过 = M, 虽然有正,有负数, 但是最多C个不同值感觉就是被这个有正有负卡住了

实际上这里的负的绝对值全部小于等于 Bi, 所以可以看成全正,!!! 和也不用考虑C的绝对值, 而是直接A B的绝对值

哦以及求数组中每个位置结尾前面k个中的最小还可以这样binary逼近的写!,没写过, 不这样的话, 就上个单调队列+滑窗跳点也行

感觉就是数链剖分,dsu on tree的 重轻链性质, 还不熟

然后虽然想到了 dp + 生成函数 +fft 转移, 但是向上面这样按照链拆分的没有想过, 想的还是 u和所有子节点的关系

也就是说如果感觉有点重轻链的感觉, 可以考虑说有没有变成链的方案

参考

官方题解

CF 1709 DSU on Tree

CF Easiest HLD with subtree queries

Hachia heavy light decomposition との融合

yosupo 2015 HLD+segtree

G - Reversible Cards 2

范围

我的思路

题解

代码

Ex - Antichain

范围

我的思路

题解

回到这个问题

$h_u$ 到 计算出$f_u$ 的复杂度

我们只需要对所有 轻儿子 和 点1 做$h_u \to f_u$的计算

代码

总结

参考

$h_u$ 到计算出$f_u$ 的复杂度

我们只需要对所有轻儿子和点1 做$h_u \to f_u$的计算