Atcoder abc311

發表於 更新於 分類於 ， Disqus： 文章字數： 2.3k 所需閱讀時間 ≈ 8 分鐘
Ex(HLRecDP)

https://atcoder.jp/contests/abc311/tasks/abc311_h

Ex - Many Illumination Plans

N点，根为1，树

点有b[i],w[i],c[i]=0/1

Q(v) = $\max \sum b_i, i\in U$ ，其中U是，v的子树U, 任意多次 删除点 并将子点和父节点相连， 最终满足$\sum w_i \le X$ 且 所有边的端点的c不同

求$Q(1),Q(2),…,Q(N)$

n 200

$X \in [0,50000]$

$W_i \in [0,X]$

$B_i\in [0,10^{15}]$

3s

1024mb

我的思路

先考虑其中一次的问题求解,

也就是给定一个有 点b[i],w[i],c[i]=0/1的树

然后删除点，让sum b尽量大，且满足 颜色 和w和的条件

dp[v] = w->b 保留v, v以下的和为w, 能得到的最大b

根据限制 传递时 只和 w与v的颜色有关

这样的问题是，要转移的话，每个v需要的就是所有后继不同色的点，并且还要考虑 后继点的关系

改一改

dp[v][c] = map<> w->b v或以下对上颜色贡献为c 和为w, 能得到的最大b

这样就是3个分支

  • 选择v，w[v] + dp[u][c[w]^1]的合并
  • 不选择v，颜色=0 的 dp[u][0] 的合并
  • 不选择y，颜色=1 的 dp[u][1] 的合并

状态数 $O(n X)$ ,但转移代价似乎有点大，可以启发式合并吗？

然后启发式合并的一点是 每次会有一个很大的状态是不变的，每次把新增的相对小的状态向大的状态里塞，而这里每次选择v的话，可能有一个大的偏移

而且如果w是1,2,4,8,这样的话，只需要16个,2^16=65536 就可以让状态是满的

一个想法是 能不能 强制 让 b随着w单调递增，这样即可以让状态是连续的，又可以保证非严格单调递增

用更小的w 对应更大的b 去覆盖了更大的b， 如果这样的到了答案，那么对应选择的w一定是大与等于 实际的w的，不会不合法？

那如果有最优方案，关心对应的同样的w，如果被其它覆盖了，那么b一定更大，且有对应的合法w方案

这样的话 每个 dp[v][c] = 一个非严格单调递增的数组w2b

需要合并n次? 如何高效的合并？ merge(A,B) = C, C[i] = max(A[j]+B[i-j],j=0..i)

单调递增也保证不了 变化程度

题解

一样的dp想法， O(NX^2), 显然过不了

https://qiita.com/tmaehara/items/4b2735e56843bad89949

https://arxiv.org/abs/1807.04942

注意到的是 因为合并每次都是很多状态之间合并 所以代价是(X^2)，而如果状态单独增加一个点，那么 代价只是X

那么每个点 会对它到根的 有影响, 所以传递 dfs(u, array<会有影响的dp>&), 一边深度搜索，一边逆向dp贡献

这官方代码,悟了好一会儿, 改造了下

  • 传入的dp 都是祖先节点还未操作的，然后兄弟节点，和祖先的子节点放入
  • 每次实际的操作 其实只有 chmax,其它都是移动操作，所以实际操作还是单点插入
  • 把题解的 ret以后取下标修改一下成下面的，其实会发现，只有C[u] = retidx 时才会影响，不等的时候都是虚空操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function dfs(u, const &dp, retidx):
	// 处理的是不插入u,而是u的儿子及更深插入 retidx 颜色
	ret[retidx] <- dp
	for v in {children of u} do
		ret[retidx] <- dfs(v, ret[retidx], retidx)
	end for
	
    // 插入u,注意到点相同只是改变顺序不会影响结果，所以u子节点及更深擦汗如retidx^1, 再插入u
	if C[u] == retidx: // 不等的时候 运算的结果也没有用
	    ret[retidx^1] <- dp
		for v in {children of u} do
			ret[retidx^1] <- dfs(v, ret[retidx^1], retidx^1)
		end for
		for i = 0 to X - W[u] do
			chmax(ret[C[u]][i + W[u]], ret[C[u] ^ 1][i] + B[u]) // 唯一实际操作
		end for
	return ret[retidx]

然后这是 官方题解的代码，感觉通过简化混在一起了，需要一点This DP is quite irregular, requiring a smart thought

1
2
3
4
5
6
7
8
9
10
11
function dfs(u,const &dp)
  Dp[0] <- dp
  Dp[1] <- dp
  for v in {children of u} do
    Dp[0] <- dfs(v, Dp[0])[0]
    Dp[1] <- dfs(v, Dp[1])[1]
  end for
  for i = 0 to X - W[u] do
    chmax(Dp[C[u]][i + W[u]], Dp[C[u] ^ 1][i] + B[u])
  end for
  return Dp

然而这样如果每层dp分叉，在最坏的情况下是 树是一条链，$O(2^N)$次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function dfs(u, const &dp)
  if u 非叶子 :
    h = (heavy child of u)
    Dp <- dfs(h, dp) // 首次访问重儿子，注意到所有点首次访问的时候，就是父节点&dp的初始状态
    for d in {children of u} / {h} do // 除了重儿子
      Dp[0] <- dfs(d, Dp[0])[0]
      Dp[1] <- dfs(d, Dp[1])[1]
    end for
  else:
    Dp[0] <- dp
    Dp[1] <- dp
  end if
  for i = 0 to X - W[u] do
    chmax(Dp[C[u]][i + W[u]], Dp[C[u] ^ 1][i] + B[u])
  end for
  return Dp

复杂度分析， 直接到上面语句，令$f(size(u))$ 为$u$向下$dfs(u,dp)$的复杂度，对应

$f(size(u)) \le f(size(h)) + 2f(size(v_2))+…+2f(size(v_{size(u))}) + O(X)$

其中$f(size(h))$ 对应第4行, 2倍对应 两个Dp[0],Dp[1]赋值，$O(X)$对应 chmax

然后因为 $f(n)$是$n$的多项式复杂度，所以 让右侧尽量大，则是让其他点都为0????????????????哇好像很有道理的样子

$f(size(u)) \le f(size(h)) + 2f(size(u)-size(h)-1) + O(X)$

这里的问题就是，虽然实际上可能在chmax的时候操作为很少，但是都看作$O(X)$这样这里操作复杂度稳定了之后，复杂度就只和大小有关系了，而复杂度和大小有关系以后，多项式就是$O(n^?)$, 所以后面合并会更大（而这？？ 总感觉有点小怪小怪的，因为如果是精确的次数计算相关的多项式，并不一定拆分以后比和起来大）

然后因为 认为复杂度和n正相关，+重儿子,

$f(size(u)) \le 3f(\frac{size(u)-1}{2}) + O(X)$

$f(n) = O(n^{\log_2^3}X) = O(n^{1.59}X)$

  • By the way, regarding the spacial complexity, stepping down to a light child requires reserving a DP table of size $O(X)$, so it is $O(X \log N)$.

回到题目，上面的做法是对于指定根的做法。

同样注意到，当求自根而下的全重链时，上层传下来的dp都是初始状态，所以其也是最终答案

而其它的dfs中，dp都有额外的值。

办法是 再次利用轻重链 关系

令$g(n)$ 为计算子树节点大小为n的答案的复杂度

$g(n) \le f(n_1)+g(n_1)+g(n_2)$

类似的 $g(n)\le 2g(\frac{n-1}{2}) + f(n)$, 所以$g(n) =O(N^{1.59}X)$

代码

https://atcoder.jp/contests/abc311/submissions/49390779

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
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
#define per(i,a,n) for (int i=(n);(i--)>a;)
const int N = 200;
ll read(){ll r;scanf("%lld",&r);return r;}
const ll INF=0x3f3f3f3f'3f3f3f3f;
int X;
tuple<ll,int,int> bwc[N+10];
vector<ll> ans;
vector<int> g[N+10];
array<vector<ll>, 2> dfs(int u, const vector<ll>& dp, bool fromroot) { // dp[sum w] = max sum b
  auto chmax=[](ll& a, ll b) { a = max(a, b); };
  array<vector<ll>, 2> ret;
  auto [b,w,c] = bwc[u];
  if (g[u].empty()) { // 叶子
    ret[0] = ret[1] = dp;
  } else {
    ret = dfs(g[u][0], dp, fromroot); // 重儿子
    rep(i,1,g[u].size()) rep(t,0,2) ret[t] = dfs(g[u][i], ret[t], false)[t]; // 其它儿子, 轻链dp非初始状态
  }
  rep(i,0, X - w + 1) chmax(ret[c][i + w], ret[c ^ 1][i] + b); // 使用点 u
  if (fromroot) { // 从'根'向下的重链 dp是空的, 会更新答案时
    rep(i,0, X - w + 1) chmax(ans[u], ret[c ^ 1][i] + b); // 更新答案
    rep(i,1, g[u].size()) dfs(g[u][i], dp, true); // 对于轻链, 此时dp为初始数组
  }
  return ret;
}

int main() {
  int n=read();
  X=read();
  vector<int> fa(n, -1), sz(n, 1); // [0,n), 父节点, 子树大小
  rep(c,1,n) g[fa[c] = read()-1].push_back(c); // 0-index
  per(i,0,n) { // 保证父节点序号小于子节点
    if (i) sz[fa[i]] += sz[i];
    sort(begin(g[i]), end(g[i]), [&](int j, int k) { return sz[j] > sz[k]; }); // 按子树大小排序子节点
  }
  rep(i, 0, n) bwc[i]= {read(),read(),read()};
  ans=vector<ll>(n,0);
  vector<ll>dp(X + 1, -INF);
  dp[0] = 0;
  dfs(0, dp, true);
  for(auto o:ans) printf("%lld\n",o);
}

总结

G 开了一下不应该

Ex

且不说后面的优化，这样在dfs中，贡献式的dp,还是第一次见

然后后面的dsu-on-tree类似的 重轻处理，可以说，见的次数越来越多，虽然不一定每次都能很好的分析复杂度，但是有这个手感倒是很自然了

然后最后这里，对于单点求和所有点求的变化，竟然不是处理过程中的分发变化，而是再度利用轻重的性质

正着dfs,倒着贡献，好怪，再看一眼，好怪

参考

官方题解

https://www.luogu.com.cn/problem/solution/AT_abc311_h

https://zhuanlan.zhihu.com/p/648384218