Atcoder abc293

發表於 更新於 分類於 ， Disqus： 文章字數： 718 所需閱讀時間 ≈ 2 分鐘
Ex(树,DP,轻重链)

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

Ex - Optimal Path Decomposition

n 点树

找最小整数k，使得有方案满足染色

  • 每个相同具体颜色，连通且简单路径
  • 树里所有简单路径 最多K种颜色

n 2e5

2s

1024mb

我的思路

这第一眼上去像是重轻儿子

第二眼上去像是树上DP

虽然具体的染色的情况 不和 K直接相关

但是 当两个不同颜色链的端点相邻，那么把它们染成同样的颜色，得到的K不会比之前的更差

dp[u][u是否可以向上连] = {u的子树中最多颜色的路径，从u向下最多颜色的路径}

显然 子树cnt >= u向下

看起来是一个 O(n^2) 的状态

而从u 向下最多颜色的路径 <= u到最深叶子的

如果有办法 把这个缩减这个向下颜色的路径的维度

然而根据轻重儿子的链式方法，根到任何叶子最多经过O(log(n)) 条不同的重链

所以如果直接 轻重链方案，那么方案 <= 2log n

所以 dp[u][u是否可以向上连][u向下最多的颜色的路径 <= 2log n] = u子树中最多颜色的路径

似乎就能做了?

代码

https://atcoder.jp/contests/abc293/submissions/41841031

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
47
48
49
50
51
52
53
54
55
56
57
58
59
#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 (ll i=n;i-->(ll)(a);)

// 2 * math.log(200000)/math.log(2) = 35.219280948873624
const int lim = 50;
const int INF=0x3f3f3f3f;
ll read(){ll r;scanf("%lld",&r);return r;}

vector<int> e[200010];
array<vector<int>,3> dp[200010]; // dp[u][与子树连的个数][向下最多颜色] = 以下已有贡献最多颜色
auto chmin=[](auto&a,const auto &b){a=min(a,b);};
int sz[200010];
auto _=[](int siz){return min(siz,lim);};

void dfs(int u,int f){
  sz[u] = 1; // 重用
  rep(c,0,3) dp[u][c] = vector(1+2,INF);
  dp[u][0][1] = 1;

  auto merge=[&](int v){
    array<vector<int>,3> ndp;
    rep(c,0,3) ndp[c] = vector(_(sz[u]+sz[v])+1,INF);
    rep(i,1,_(sz[u])+1) rep(c0,0,3) rep(j,1,_(sz[v])+1) rep(c1,0,3) {
      chmin(ndp[c0  ][max(i,j+1)], max({dp[u][c0][i], dp[v][c1][j], i+j})); // 不连u-v
      if(c0 < 2 and c1 < 2){
      chmin(ndp[c0+1][max(i,j  )], max({dp[u][c0][i], dp[v][c1][j], i+j-1})); // 连 u-v
      }
    }
    sz[u] += sz[v];
    rep(c,0,3) {
      dp[u][c].resize(_(sz[u])+2,INF);
      rep(j,1,_(sz[u])+1) dp[u][c][j] = ndp[c][j];
    }
  };

  for(auto v:e[u]) if(v!=f){
    dfs(v,u);
    merge(v);
  }
}

int main(){
  int n=read();
  rep(i,1,n){
    int u=read();
    int v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1,-1);
  int ans = INF;
  rep(c,0,3) rep(i,1,_(sz[1])+1) chmin(ans, dp[1][c][i]);
  assert(ans <= lim);
  printf("%d\n",ans);
  return 0;
}

总结

Ex

虽有轻重链的知识，但整体核心的部分和 CF1830D 是一样的，就是通过数学降低dp的剩余维度的大小

竟然又自己做出了一个红题,虽然只是abc的2831评分

参考

官方题解