Atcoder abc340

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
G(虚树,树上DP,lca,重轻链)

https://atcoder.jp/contests/abc340

G - Leaf Color

n点树，点有颜色，问又多少个 导出子图的“端点”都是同色 mod 998244353

n 2e5

2s

1024mb

我的思路

每个颜色单独考虑

那实际上是选择同色的点，要让任何三点不共线，没想到怎么统计

题解

我一直没想通的地方

1
2
3
4
5
      1
  0(x)   0
 0
0(y)
1 1

是 如何不重不漏

例如这里 的y 是可以在选择下面两个1的时候，作为lca的

而x 是不能的

而根部的1是可以的

利用树型 令 f[u] 为选择u 以及u向下的多个 末端是1的方案数

这里对 u的要求没有

那么 $f[u] = \prod (f[v]+1)$

其中$v$是$u$的子节点，而 $+1$ 表示 $v$及其子树不选的情况,

而如果 全部都不选 则对应到 所有的$+1$相乘，这种情况只有 $u$是可单独选时才可行，所以u不能单独选的时候需要 $-1$

$f[u]=(\prod (f[v]+1))- [u!=1]$

考虑贡献

1
2
3
4
5
      1
  0(x)   0
 0
0(y)
1 1

这里u和v 以及它们之间的f 都是3

然而只有u 是可以选的

也就是 一个0节点的 单个分支 的所有选法不构成贡献

$ans += f[u]-\sum f[v]$ 其中 $u$是不可单独选,$v$是$u$的子节点

$ans += f[u]$ 其中 $u$可单独选

剩下的就是每个颜色单独提出来了，因为对于颜色c,显然 每个非c颜色的点要保留，那么它是 某些颜色c的lca,而每多一个lca,至少需要多一个颜色c节点，所以拆出来的树的节点总和,不多于2n个节点

代码

https://atcoder.jp/contests/abc340/submissions/52926899

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD = 998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;

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

ll read() { ll r; scanf("%lld", &r); return r; }

#define N 200010
int a[N];
vector<int> e[N];

int sz[N],fa[N],dep[N];
void dfs1(int u,int F) {
  per(i,0,size(e[u])) if(e[u][i]==F) {
    swap(e[u][i],e[u].back());
    e[u].pop_back();
  }
  sz[u]=1;
  dep[u]=dep[fa[u]=F]+1;
  rep(i,0,size(e[u])) {
    int v=e[u][i];
    dfs1(v,u);
    sz[u]+=sz[v];
    if(sz[v]>sz[e[u][0]]) swap(e[u][0],e[u][i]); // 重儿子, size
  }
}

int dfn[N],root[N];
void dfs2(int u,int R,int &cur) {
  dfn[u]=cur++; // dfs number
  root[u]=R;
  if(sz[u] == 1) return; // 叶子
  dfs2(e[u][0],R,cur); // 重儿子
  rep(i,1,size(e[u])) dfs2(e[u][i],e[u][i],cur); // 轻儿子
}
int lca(int u,int v) {
  for(;root[u]!=root[v];u=fa[root[u]]) if(dep[root[u]]<dep[root[v]]) swap(u,v);
  return dep[u]<dep[v]?u:v; // u,v在一条重链上
}
vector<int> eg[N];
vector<int> fake(vector<int> v) {
  auto cmp=[&](int x,int y){return dfn[x]<dfn[y];};
  vector<int> ans=v;
  sort(v.begin(),v.end(),cmp); // 按照 dfs序 sort
  rep(i,1,size(v)) ans.push_back(lca(v[i-1],v[i])); // dfn相邻的lca
  ans.push_back(1); // 根节点, 加了简化处理不影响结果
  sort(ans.begin(),ans.end(),cmp);
  ans.resize(unique(ans.begin(),ans.end())-ans.begin()); // 去重
  rep(i,1,size(ans)) eg[lca(ans[i-1],ans[i])].push_back(ans[i]);
  return ans;
}
mint f[N];
void dfs(int x,int C,mint&ans) {
  f[x]=1;
  mint tot=0; // 单儿子的方案和, 在根非颜色时 不贡献
  for(auto i:eg[x]) {
    dfs(i,C,ans);
    tot+=f[i];
    f[x]*=(f[i]+1);
  }
  if(a[x]!=C){
    f[x]-=1;
    ans+=f[x]-tot;
  }else{
    ans+=f[x];
  }
}
vector<int> c2i[N]; // color to index
int main() {
  int n=read();
  rep(i,1,n+1) {
    a[i]=read();
    c2i[a[i]].push_back(i);
  }
  rep(i,1,n) {
    int u=read();
    int v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs1(1,0); // 父节点, 子树大小, 深度, 重儿子
  int cur=0;
  dfs2(1,1,cur); // 处理重链
  mint ans=0;
  rep(i,1,n+1) if(c2i[i].size()) {
    vector<int> v=fake(c2i[i]);
    dfs(1,i,ans);
    for(auto j:v) eg[j].clear();
  }
  printf("%d",ans.val());
  return 0;
}

总结

g:

树上dp没想到真不应该，不过虚树抽出来还是第一次学

虚树 的建立法说白了是

  1. 计算点的dfs顺序 dfn[u]
  2. 把同色点按照 先序dfn排序
  3. 把按照dfn序的相邻点的 lca加入就好！！
  4. sort+去重 同样按照 dfn序
  5. 建立新树，那么 点[i-1]和点i,有两种关系
    1. 点[i-1]是点[i]的父节点
    2. 点[i]的父节点是 点[i-1]的祖先节点
1
2
3
4
        1
   2         9
 3   6    10   13
4 5 7 8 11 12 14 15

第一次见用轻重链来做 lca的！！怎么感觉比 倍增的智力负担还小！

1
2
3
4
int lca(int u,int v) {
  for(;root[u]!=root[v];u=fa[root[u]]) if(dep[root[u]]<dep[root[v]]) swap(u,v); // 每次把root深度更深的做转移
  return dep[u]<dep[v]?u:v; // u,v在一条重链上
}