Educational Codeforces Round 116

發表於 更新於 分類於 ， Disqus： 文章字數： 2.6k 所需閱讀時間 ≈ 9 分鐘
F(树,数学推演)

CF tracker

Edu List

https://codeforces.com/contest/1606

F. Tree Queries

根1 n点树

q个询问: 每次给 点v, 数k

删除任意点 任意顺序 (根和v不能删除)

每次删除u: 让u的子节点的父节点 = fa[u]

求max(childcount(v) - 删除点数 * k)

每个询问独立从初始树询问

范围

n 2e5

q 2e5

k [0,2e5]

6s

512mb

我的思路

k == 0 时， 显然贪心就完了，要让一个后代点成为v的子节点, 就是要让它到v之间的路径上的其它点都删除

所以 v最多能有它的子树中叶子个点

最少就是不删除时它直接的节点数，为了让答案更大，所以节点一定在这个范围之间

如果知道 v 得到x个子节点的最少删除数量cnt[v][x]， 那么x - cnt[v][x]*k

几个问题，

第一cnt没法计算所有因为空间和时间复杂度都是O(n^2)的？

第二即使暴力算cnt, cnt并不一定连续, 例如 1-2-3,2-4,2-5, 那么其实1的子节点要么1个要么3个，虽然可以乱删到2个，但是那种的过程不是贪心方向的

第三 即使有了cnt, 那么对于给定的v和k 还要枚举x才行 会达到O(nq)

一个方向，离线掉，看如何批量的处理计算

总有一点点斜率维护的感觉，如果斜率是 凸的，那么只是去找斜率k的切点

题解

暴力的方法，另f(v,k) 是 答案

$f(v,k) = \sum_{u\in children(v)} max(1,f(u,k)-k) $ !!!!!!

因为如果不删除u,那么u的子树怎么处理也不影响v的子节点，而u本身对答案贡献是1 右侧无贡献

如果删除u, 也就是这里的 -k, 那么对于直接考虑f(u,k)的情况来看，就是f(u,k)的结果的u子节点全部变成v了， 那么这个对应的贡献也是 同样的!!!!!

但这离线后也是 O(n min(k,q))的

优化

然后有 f(v,k-1) >= f(v,k), 显然 对于v,k的任意方案, 的v,k-1的同样方案的f不小它，因此 最大的f(v,k-1) >= 最大的f(v,k)

然后又是神奇的推演!!!

如果对于v,k来说最优方案中, u是被删除, 那么说明 $f(u,k) - k \ge 1$, 根据max

那么$f(u,k-1) - (k-1) \ge f(u,k) - k + 1 \ge 1 + 1 > 1$, 说明在v,k-1中依然要删除u

换句话说u的某个子节点v, 有一个最大的k(显然不能无限大), 在<=这个k 的情况下,都是要删除u的

所以要找 maxk(u) ,也就是v的子节点u的最大的k让它应该被删除

显然自下而上(dfs)

对于每个点，存两个值 — 从它子树中应该删除的点数, 这个点最优能有的子节点个数. 用这两个数能容易酸楚maxk(u)

对于个点u, 如果点是被删除的(也就是, the event corresponding to this vertex is processed), 点的这两个值应该加到它当前的父节点(通过 并查集合可能快速找到当前父节点; 不要忘记新父节点 删除点数+1)

然后更新当前父节点 的maxk的结果 and change the event corresponding to 当前父节点( 注意 父节点的maxk 不应该大于 被删节点的 maxk).

Okay, this allows us to calculate when it’s optimal to delete each vertex. But how do we answer queries? One of the ways to do this is to process queries in the same event processing algorithm (and for every value of k
, we first “remove” the vertices u with opt(u)=k , then process the queries). There is an issue that when we remove a vertex, it can affect the answer not only for its current parent, but also for the vertices that could be its parents, but are already deleted; to handle this, instead of adding the values of the deleted vertex only to the values of its current parent, we perform an addition on the whole path from the vertex to the current parent (excluding the vertex itself). This path addition can be performed with a Fenwick or Segment tree over the Eulerian tour of the tree, and this yields a compexity of O(nlogn) , though with a high constant factor.

还是感觉有点怪， 这里的什么event processing method, 感觉就是触发更新一样，这个中间值的变化 就感觉不知道最小依赖是个啥

因为从数学上讲， 如果点u被删除，那么它向上贡献时， 它向下的部分一定是个连通块，所以当一个点被删除时，从删除统计上，只会直接影响它的父节点，而它的祖先节点要是被影响，也是通过它的父节点被删除而进行的，所以每次删除只会更新一个点

从而不会出现“插队”的问题，(虽然当前状态 都没达到删除的k, 但是如果和起来可以让一些点达到删除的k, 因为如果这种情况发生,那么最深的点没有更深的操作则不应该被删, 而它不删带来的更优，则和最深矛盾)

代码

https://codeforces.com/contest/1606/submission/193517336

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
using namespace std;

struct Vertex {
  int cost;
  int depth; // -1 则是询问, 否则是树上点深度
  int idx; // depth == -1 则idx 是询问idx, 否则是树上的点
  Vertex() {};
  Vertex(int cost, int depth, int idx) : cost(cost), depth(depth), idx(idx) {};
};

// 大cost(随着k变小，删除的保持删除, 所以从大到小枚举)
// 大depth(节点删除先于询问，深节点先于浅节点
// index小先(没啥影响，主要用来set判重复)
bool operator <(const Vertex& a, const Vertex& b) {
  if(a.cost != b.cost) return a.cost > b.cost;
  if(a.depth != b.depth) return a.depth > b.depth;
  return a.idx < b.idx;
}

struct DSU {
  vector<int> p; // 保证并查集的根也是 深度最浅的
  int get(int x) { return (p[x] == x)?x:(p[x]=get(p[x])); }
  void merge(int x, int par) { p[x] = par; } // 保证p[par] = par 且par是x的祖先 且当前未删除
  DSU(int k = 0) {
    p.resize(k);
    iota(p.begin(), p.end(), 0);
  };
};

const int N = 200000;

int n;
vector<int> g[N+10]; // 树
int p[N+10]; // 父节点
int d[N+10]; // depth
int tin[N+10], tout[N+10]; // 树的dfs续展开 u => [in[u]...out[u]]

void dfs(int &T,int v,int par,int dep){
  tin[v] = T++;
  p[v] = par;
  d[v] = dep;
  rep(i,0,size(g[v])) if(g[v][i] == par) { // remove father
    swap(g[v][i],g[v].back());
    g[v].pop_back();
    break;
  }
  for(auto u: g[v]) dfs(T, u, v,dep+1);
  tout[v] = T;
}
pair<ll, ll> operator+(const pair<ll, ll>& a, const pair<ll, ll>& b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
#define SEG_ROOT 0,0,n
#define SEG_L (o*2+1)
#define SEG_R (o*2+2)
#define mid ((l+r)/2)
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r
pair<ll, ll> seg[4*N + 10]; // {child count, remove count}
pair<ll, ll> get(int o, int l, int r, int ql, int qr) {
  if(ql <= l && r <= qr) return seg[o];
  pair<ll,ll> res = {0,0};
  if(ql < mid) res = res+get(SEG_L_CHILD, ql, qr);
  if(qr > mid) res = res+get(SEG_R_CHILD, ql, qr);
  return res;
}

void add(int o, int l, int r, int pos, pair<ll, ll> val) {
  if(l == r - 1) seg[o] = seg[o] + val;
  else {
    if(pos < mid) add(SEG_L_CHILD, pos, val);
    else          add(SEG_R_CHILD, pos, val);
    seg[o] = seg[o] + val;
  }
}

pair<ll, ll> get_vertex_value(int v) { return get(SEG_ROOT, tin[v], tout[v]); }

void add_on_path(int x, int y, pair<ll, ll> val) { // x is a descendant of y
  // in[p[y]]...in[y]...in[x]...out[x]...out[y]...out[p[y]]
  //       - [             +]
  add(SEG_ROOT, tin[x], val);
  if(p[y] != -1) add(SEG_ROOT, tin[p[y]], make_pair(-val.first, -val.second));
}

int calculate_cost(int v, ll correction) { // k <= correction
  auto [ch, rm] = get_vertex_value(v); // 当前v已经删除的个数，和子节点个数, 这样可以推出最大的k 让贡献 >= 1
  // child - (remove + 1) * k >= 1
  // (child-1) >= (remove+1)*k , ch 可能为0, (ch-1+(rm+1))/(rm+1) - 1
  ll k = (ch+rm)/(rm+1)-1;
  return min(k, correction);
}

int main() {
  n = read();
  rep(i,1,n){
    int u=read()-1;
    int v=read()-1;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int q=read();
  vector qv(q,0);
  vector qk(q,0);
  rep(i,0,q){
    qv[i]=read()-1;
    qk[i]=read();
  }
  // 读入 --- end

  int T=0;
  dfs(T,0,-1,0); // 初始化树
  DSU dsu(n);

  set<Vertex> pq;
  vector<Vertex> curv(n); // curv[点] => 在pq中的值
  rep(i,0,n) add_on_path(i, i, {g[i].size(), 0}); // {child count, remove count}
  rep(i,1,n) {
    curv[i] = Vertex(calculate_cost(i, 200000), d[i], i); // 计算初始状态下, 每个节点被删支持的最大的k
    pq.insert(curv[i]);
  }
  rep(i,0,q) pq.insert(Vertex(qk[i], -1, i)); // 询问

  vector<ll> ans(q);
  while(!pq.empty()) {
    Vertex z = *pq.begin();
    pq.erase(pq.begin());
    if(z.depth == -1) { // 询问, 所有 >= k的 节点已经处理完了
      auto [ch,rm] = get_vertex_value(qv[z.idx]); // 获取节点状态即可
      ans[z.idx] = ch - rm * z.cost;
    } else { // 处理点删除
      int v = z.idx; // 点
      int pv = p[v]; // 直接父节点
      int newtop = dsu.get(pv);
      auto [ch,rm] = get_vertex_value(v);
      add_on_path(pv, newtop, {-1+ch,rm+1}); // 注意到虽然有些父向节点 已经删除了 但依然需要更新只是不会再参与删除
      if(newtop != 0) { // 更新它的父节点
        pq.erase(curv[newtop]);
        curv[newtop].cost = calculate_cost(newtop, z.cost); // 新的k不能比当前的还大
        pq.insert(curv[newtop]);
      }
      dsu.merge(v, pv);
    }
  }
  for(auto v:ans) printf("%lld\n", v);
  return 0;
}

总结

1h 20min 内做了A~E

这D很难吗怎么评分是红色，还是现场时题意有问题？

F. 哎 我好菜啊 这第一个暴力的式子完全没发现，这个 事后看上去很显然的拆解!!!!!!

学一手 关于点的函数 拆解成子节点的同类递归函数!!!! 印象中应该是第一次遇到

没有智慧

event processing method 还是感觉好怪啊，这相当于 中间会有不少 并不影响结果的 [删除个数,子节点数]的记录, 只是需要处理时都是有效的

总体就是: 对点的表达式转换成, 它子节点类似的表达式, 分析出表达式的单调性(<=某个k 则一定要删除), 于是枚举k从大到小, 维护每个点当前已经删除和儿子节点数(这里不会发生穿透, 也同时有局部性), 一个点的删除带来的更新 可能让它新的父节点的k更大,但因为连通关系又不能更大(否则它新父亲在它之间就该被删除), 然后DSU维护的是 dsu[u]=u被删除后它祖先最近未被删除的, 更新每个点的状态就是靠树上的链的批量 加法，通过树dfs序展开和线段树/fenwick维护就行, 注意的是一个点删除它向上到未被删除一条线的点都需要更新结果

看洛谷题解区，似乎有用答案不超过 n/k 种 来做根号分治!! 啊 好有道理

参考

官方

洛谷