Educational Codeforces Round 122

發表於 2023-01-18 更新於 2024-04-11 分類於 Codeforces ， Edu Disqus：文章字數： 3k 所需閱讀時間 ≈ 10 分鐘

E(最小生成树)F(树,数学,树链剖分,线段树,Link/Cut tree)

CF tracker

Edu List

https://codeforces.com/contest/1633

E. Spanning Tree Queries

给n点,m边一个连通无向图

k个询问, 每次一个xi

你需要找一个生成树, 让 sum |wj-xi| 最小, wj为生成树的边的权重, 不需要输出具体方案

前 p个询问具体给出 xi

[p+1~k] 的询问通过 q[j]=(q[j-1]a+b)%c 给出

输出所有询问的结果的xor

范围

n 50

m 300

wi, xi [0,1e8]

p 1e5

k 1e7

c [1,1e8]

256mb

我的思路

对于一个具体的一个询问, 那么就是经典的最小生成树算法, 让边权 = |wj-xi| 即可

但如果把边排序了并记录边的id

如果x变化, 但是排序后id顺序没有变, 那么最小生成树选择的边就不会边(虽然边权重变了)

那么排序后会有多少种情况呢, 感觉上比 binom(50,25) 还多, 想x分割大于和小于的边,两个穿插

如果这个情况少, 那就变成统计情况内的边选择, 和对应>x小于x的个数与和来计算了

p 1e5 n 50 , m 300 是可以接受暴力的

但是 k 1e7 一定要实现某种批量算法

题解

考虑Kruskal’s algorithm 算法, 就是按 |wi-x|从小到大排序, 一个一个边处理

x=0时, 全部按照w排序, 随着x增加两个点交换顺序时, 表示x经过了两个点的均值, 所以最多O(m^2) 种顺序

剩下的就和我想的一样了, 每种情况分类暴力处理就完了, 记录下w的和和 x的权重和

https://codeforces.com/contest/1633/submission/189907196

F. Perfect Matching

给一个n点的树, 和n-1边, 只有点1激活

3种询问

激活点v(保证之前未激活,且至少一个相邻点是激活的), 激活后, 你需要选边的子集合, 每个激活的点要恰好只在一条边上, 每个未激活的点要都不在边上,(就是选一组边匹配掉所有激活点), 输出选的边的 index的和, 没有方案输出0
只会紧跟在询问1以后, 至多10次(如果之前是0,直接输出0), 按升序输出选的边的index
结束询问

要输出了才能读下一个输入

范围

n 2e5

12s

512mb

我的思路

搞这么花里胡哨, 其实就是要强制在线一下

然后用3来结束也没啥意义, 反正不会超过n, 因为每个点最多激活一次

把1看作根, 显然, 所有点都不会比它子节点先激活, 所以每个结点被激活时, 如果有匹配方案, 那么它一定和它父节点匹配

但是这个匹配不一定持久

1
2

1-3
1-2-4

按照2,3,4 的顺序激活, 2的时候, 1-2是方案, 但是到了4的时候, 1-3,2-4是方案, 1-2被拆掉了

但是注意到每个点要么和它父亲匹配要么和儿子匹配, 因为深度奇偶性, 直接就可以上二分图

每次看成增加一个点和这个点与它父向节点的双向边, 然后通过该点做匹配,

不太相同的是增加可能是左侧也可能是右侧

然后直接边选择变化来得到新的index和

每次匹配数量增量为0或1

当匹配数 * 2 == 点数时就可以了

似乎就没了??

好像复杂度不太对

题解

1作为顶点, 如果是完美匹配,每次找深度最大的节点, 一定和它的父节点匹配, 删除这个匹配并循环到没有点

那么从这个过程中, 一个深度最深的节点是它的父节点的唯一子节点, 匹配方案都是唯一的

那么一个节点的子树节点数的变化要么 -2 要么-0, 也就是一个节点的子树节点数在过程中奇偶性不变

所以给所有顶点标上奇偶(会随着增加新的点而变化), 而删除时一定是儿子奇数点, 父节点偶数点

所以再说就是所有奇数点和它父节点匹配(保证不冲突) , 但是这每次是O(n)的, 每个偶点又至少有一个奇数子女(即使在无法匹配下, 因为点 = 子节点奇偶的和+1 , 所以子节点和=奇数,所以至少一个奇数子节点)

完美匹配需要:

每个点偶数点恰好一个奇数子节点
每个奇数节点有偶数父节点

这意味着, 奇数节点个数 == 偶数节点个数 !!!!!!!!!!!!!!!!!!!!!!!!!! ( 其实二分图上也可以得到类似性质的, 但是不是子树节点数的奇偶, 而是深度的奇偶, 还是不一样)

(感觉题解这里证明搞麻烦了, 因为奇偶性不变, 加上匹配过程是叶子和叶子的父亲配, 所以一定奇偶成对啊)

而更好的性质是, 这不光是必要, 还充分!!!!

因为每个偶至少一个奇数, 所以每个偶数和它奇数配, 这样所有偶数配完了所有奇数

那么问题变成维护节点的奇偶性, 众所周知, 增加一个叶子节点,就是它到根的所有节点的奇偶性颠倒

需要上Link/Cut tree(动态树) + 线段树维护了

代码

https://codeforces.com/contest/1633/submission/189959199

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

#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

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

const int N=200000;

pair<ll,int> operator +(const pair<ll,int>& a, const pair<ll,int>& b) {
  auto [a0,a1]=a;
  auto [b0,b1]=b;
  return {a0+b0,a1+b1};
}

pair<ll,int> operator -(const pair<ll,int>& a, const pair<ll,int>& b) {
  auto [a0,a1]=a;
  auto [b0,b1]=b;
  return {a0-b0,a1-b1};
}

pair<ll,int> full[4*N+10]; // 区间上所有 [edge index sum, edge count]
pair<ll,int> seg[4*N+10]; // 当前区间选中的真实的 [edge index sum, edge count], 并没有实际记录奇偶, 而是默认奇数选择, 翻转奇偶就是翻转选择, 这样记录的就是所有奇数节点的 向上的选择条数
int lazyflip[4*N+10]; // lazy flip, 已作用于当前区间, 未作用于子区间

void flipo(int o){ // 线段树上单节点操作
  lazyflip[o] ^= 1; // lazy tag
  seg[o] = full[o]-seg[o]; // 翻转奇偶 <=> 翻转选择
}

void down(int o) {
  if(lazyflip[o] == 1) {
    flipo(SEG_L);
    flipo(SEG_R);
    lazyflip[o] = 0;
  }
}

void up(int o) {
  full[o] = full[SEG_L] + full[SEG_R];
  seg[o] = seg[SEG_L] + seg[SEG_R];
}

// [l,r) 设置 [pos] => {边id, count}
void setVal(int o, int l, int r, int pos, pair<ll,int> cur) {
  if(l == r - 1) { // 叶子
    full[o] = cur;
    seg[o] = cur;
    lazyflip[o] = 0;
  } else {
    down(o);
    if(pos < mid) setVal(SEG_L_CHILD, pos, cur);
    else          setVal(SEG_R_CHILD, pos, cur);
    up(o);
  }
}

// [l,r) 对 [ql..qr) 颠倒奇偶性
void flipColor(int o, int l, int r, int ql, int qr) {
  if(ql <= l && r <= qr) {
    flipo(o);
  }else{
    down(o);
    if(ql < mid) flipColor(SEG_L_CHILD, ql, qr);
    if(qr > mid) flipColor(SEG_R_CHILD, ql, qr);
    up(o);
  }
}

// [l,r) 计算[ql,qr) 的 {sum index, edge count}
pair<ll,int> query(int o, int l, int r, int ql, int qr) {
  if(ql <= l and r <= qr) return seg[o];
  pair<ll,int> ans = {0,0};
  down(o);
  if(ql < mid) ans = ans + query(SEG_L_CHILD, ql, qr);
  if(qr > mid) ans = ans + query(SEG_R_CHILD, ql, qr);
  up(o);
  return ans;
}

int n; // 节点数
vector<int> g[N+10]; // g[u] = {...v}
int p[N+10]; // 父节点
int sz[N+10]; // 子树大小(所有点不论是否激活)
int d[N+10]; // 深度
int nxt[N+10]; // Link/Cut Tree, 每个点的nxt 指向同链上的最浅的节点, 链是自浅到深由重儿子连接而成
int tin[N+10]; // dfs 进入时刻, (在调整顺序以后, 保证重链是连续的区间
map<int, int> idx[N+10]; // idx[u][v] = edge id

pair<ll,int> sc;// 选中的边的 {index sum, count}
int active[N+10]; // 点是否激活
int active_cnt;

void dfs_sz(int v) {
  if (p[v] != -1) { // 非根
    auto it = find(g[v].begin(), g[v].end(), p[v]); // 连向边中删除父节点
    if (it != g[v].end()) g[v].erase(it); // 线性的代价, 但是 总体是O(边) 的 所以还好
  }
  sz[v] = 1;
  for (int &u : g[v]) { // 一定没有父节点
    p[u] = v; // 父节点
    d[u] = d[v] + 1; // 深度
    dfs_sz(u);
    sz[v] += sz[u]; // 子树大小
    if (sz[u] > sz[g[v][0]]) swap(u, g[v][0]); // 重儿子放第一个
  }
}

void dfs_hld(int v, int&t) {
  tin[v] = t++; // 记录每个点dfs进入时间
  for (int u : g[v]) {
    nxt[u] = (u == g[v][0] ? nxt[v] : u); // 轻儿子的链的根是自己, 重儿子的链的根和父节点链的根相同
    dfs_hld(u,t);
  }
}

// v..u的路径上 {选中边的和, 选中边的条数}, 保证v是u的祖先节点
void flipPath(int v, int u) {
  // 每次处理 nxt[u]..u 区间flip
  for (; nxt[v] != nxt[u]; u = p[nxt[u]]) flipColor(SEG_ROOT, tin[nxt[u]], tin[u]+1);
  flipColor(SEG_ROOT, tin[v], tin[u]+1); // 区间flip
}

// v..u的路径上 {选中边的和, 选中边的条数}, 保证v是u的祖先节点
pair<ll,int> getPath(int v, int u) {
  pair<ll,int> res = {0,0};
  // 每次处理展开的地方 [nxt[u]=u所在链的根,u] 对应的区间
  for (; nxt[v] != nxt[u]; u = p[nxt[u]]) res = res + query(SEG_ROOT,tin[nxt[u]], tin[u]+1);
  return res + query(SEG_ROOT,tin[v], tin[u]+1);
}

void activate_vertex(int u) {
  int eid = 0; // u向上的边的 index
  if(p[u] != -1) { // 非根
    eid = idx[u][p[u]];
    sc = sc - getPath(0, p[u]); // 获得路径上 被选边的 {index和, 条数}
    flipPath(0, p[u]);
    sc = sc + getPath(0, p[u]);
  }
  sc = sc + pair<ll,int>({eid, 1}); // u和它父节点匹配的情况
  // 对于根来说, 根节点是 {eid=0,ecount=1} 但是不会产生错误结果, 因为点奇数时 选边*2=点 不会成立, 点偶数时 根的子树大小为偶数 一定不会选这条边, 所以这里ecount其实=任何数都行, eid 同理 其实任何数都行
  setVal(SEG_ROOT, tin[u], {eid,1});
  active[u] = 1; // u 被选
  active_cnt++; // 激活的点的数量
}

int dfsSolution(int u, vector<int>& edges) { // return 当前子树大小
  if(!active[u]) return 0;
  int sz=1;
  for(auto v : g[u]) sz += dfsSolution(v, edges);
  if(sz&1) edges.push_back(idx[u][p[u]]); // 子树为奇数和父节点配对
  return sz;
}

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);
    idx[u][v] = i;
    idx[v][u] = i;
  }
  { // init_hld
    int root = 0; // 0-index
    d[root] = 0;
    nxt[root] = root;
    p[root] = -1;
    dfs_sz(root);
    int timer = 0;
    dfs_hld(root, timer);
  }
  activate_vertex(0);
  for(;;) {
    int op=read();
    if(op == 1) {
      activate_vertex(read()-1);
      auto [s,c]=sc;
      printf("%lld\n", (c*2 == active_cnt)?s:0);
    }else if(op == 2) {
      vector<int> edges;
      auto [s,c]=sc;
      if(c*2 == active_cnt) {
        dfsSolution(0, edges);
        sort(edges.begin(), edges.end());
      }
      printf("%d", int(size(edges)));
      for(auto x : edges) printf(" %d", x);
      printf("\n");
    }else if(op == 3) break;
    fflush(stdout);
  }
  return 0;
}

总结

现场171人过E

我傻了, 每次两个位置交换, 就是经过两个的均值, 所以不会有binom(50,25) 那么多,而是简单的 m^2, 数学太菜了

不过按照排序分类的思考方向, 倒是没啥问题

这样的处理的话, 后面也就不需要批量算法了而是直接的for就行了

二分图的话, 每次vis的话会达到 O(n^2)的复杂度, 过不了

这数学推导, 为啥我自己就推不了呢, 没有智力, 这个必要性显然, 充分性虽然很容易证明, 但第一眼还没觉得显然

最后的维护, Link/Cut tree 第一次见, 不过大概的思路是, 树上点到根的批量操作可以用link/cut tree

LCT的原理就是通过调整重儿子为首个节点, 这样dfs先序遍历展开成数组, 在数组中的重链就会是连续的, 所以是一个连续区间, 而一个节点到根经过的不同链的条数不会超过log条, 所以每次修改都是log个区间, 每个区间通过线段树维护, 就是log级别代价, 所以是 log^2 代价就可以完成这样的操作

参考

官方