查看源代码：
OI-water-20250821.md

---
title: 每日一水（2025/8/21）
createTime: 2025/8/21
categories:
    - IT
tags:
    - OI
---

## 树剖板子

一开始没想好写什么

```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int fa[maxn];
vector<int> son[maxn];

struct chain {
    int siz[maxn], wson[maxn], dep[maxn]
    int top[maxn], dfn[maxn];
    int dft;
    
    void dfs1(int u) {
        int wsiz=0;
        siz[u] = 1;
        dep[u] = dep[fa[u]]+1;
        
        for (int v: son[u]) {
            dfs1(v);
            
            if (siz[v] > wsiz) {
                wsiz = siz[v];
                wson[u] = v;
            }
        }
    }
    
    void dfs2(int u, int tp) {
        dfn[u] = ++dft;
        top[u] = tp;
        
        if (wson) {
            dfs2(wson, tp);
        }
        
        for (int v: son[u]) {
            if (v != wson[u]) {
                dfs2(v, v);
            }
        }
    }
} ch;

struct segt {
    
};
```

## [P2418 yyy loves OI IV](https://www.luogu.com.cn/problem/P2418)

dp，转移方程是显然的

$$
f(i) = 1 + \min_{j<i}^{\text{ok}(j+1,i)} f(j)
$$

对于膜拜同一位，容易处理，多维护一个左端点之后是区间查询。

对于绝对值：令 $\texttt{yyy}=1$, $\texttt{c01}=-1$，计算前缀和 $s(i)$，则
$$
|s(i)-s(j)| \le M \iff s(i) - M \le s(j) \le s(i)+M
$$
把 $s(i)$ 当作下标之后再建一棵树即可。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;

template<int N>
struct segt {
    int a[N * 4];
    
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    inline int md(int x, int y) { return (x+y)>>1; }
    
    void build() {
        memset(a, 0x3f, sizeof a);
    }
    
    void pushup(int tn) {
        a[tn] = min(a[lc(tn)], a[rc(tn)]);
    }
    
    void add(int tn, int tl, int tr, int i, int x) {
//      if(debug)printf("[ADD] to node #%d [%d,%d], [%d]=%d\n", tn, tl, tr, i, x);
        
        if (tl == tr) {
            a[tn] = min(a[tn], x);
            return;
        }
        
        int mid = md(tl, tr);
        if (i <= mid) {
            add(lc(tn), tl, mid, i, x);
        } else {
            add(rc(tn), mid+1, tr, i, x);
        }
        pushup(tn);
    }
    
    int query(int tn, int tl, int tr, int x, int y) {
//      if(debug)printf("to node #%d [%d,%d], q: [%d,%d]\n", tn, tl, tr, x, y);
        
        if (tl > y || tr < x) {
            return inf;
        }
        
        if (x <= tl && tr <= y) {
            return a[tn];
        }
        
        int mid = md(tl, tr);
        return min(
            query(lc(tn), tl, mid, x, y),
            query(rc(tn), mid+1, tr, x, y)
        );
    }
};

const int maxn=5e5+10;
int n;
int a[maxn];
int s[maxn], bl[maxn];
int f[maxn];
segt<maxn> t1;    // 定义域：[0, n]
segt<2*maxn> t2;  // 定义域：[-n, n] 

inline void setf(int i, int x) {
    f[i] = x;
    t1.add(1, 0, n, i, x);
    t2.add(1, -n, n, s[i], x);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    t1.build();
    t2.build();
    
    int m;
    cin >> n >> m;
    
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        bl[i] = (a[i] == a[i-1])? bl[i-1]: i;
        s[i] = s[i-1] + (a[i]==1? 1: -1);
    }

    setf(0, 0);
    for (int i=1; i<=n; i++) {
        setf(
            i, 
            1 + min(
                t1.query(1, 0, n, bl[i]-1, i-1),
                t2.query(1, -n, n, s[i]-m, s[i]+m)
            )
        );
    }
    
    cout << f[n];
    
    return 0;
}
```

## [P6340 [COCI 2007/2008 #2] KEMIJA](https://www.luogu.com.cn/problem/P6340)

设构造环为 $c$，目标环为 $t$。

乍一看自由度很高，看看确定前 2 个会怎么样。那么以下的都满足这个递推公式：

$$
c_{i} = t_{i-1} - c_{i-1} - c_{i-2} \quad (3 \le i \le n+2, t_{n+1}=t_1)
$$

递推出的结果一定满足

$$
\begin{cases}
c_{n+1} = c_1 \\
c_{n+2} = c_2
\end{cases}
$$

那么答案很显然了，把 $c_1, c_2$ 设成未知数，就可以递推出一个方程组。然后解方程组即可。

如果这个方程组有无数组解，那么相当于不定方程，使用 exgcd，注意要处理 $(0, 0)$ 情况。

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

struct formula {
    int c1, c2, n1;
};

inline formula operator + (const formula &a, const formula &b) {
    return {a.c1+b.c1, a.c2+b.c2, a.n1+b.n1};
}

inline formula operator - (const formula &a, const formula &b) {
    return {a.c1-b.c1, a.c2-b.c2, a.n1-b.n1};
}

inline formula operator * (const formula &a, int b) {
    return {a.c1*b, a.c2*b, a.n1*b};
}

inline int det(int a, int b, int c, int d) {
    return a*c - b*d;
}

inline ostream& operator<< (ostream& os, formula& f) {
    cout << "(" << f.c1 << "x+" << f.c2 << "y+" << f.n1 << ")";
    return os;
}

int exgcd(int x, int y, int &a, int &b) {
//  printf("exgcd(%d, %d)", x, y);
    
    if (x == 0 && y == 0) {
        a = b = 1;  // 保证有解，所以可以乱搞 
        return 1;  // 保证 g!=0 
    }
    
    if (y == 0) {
        a = 1;
        b = 0;
        return x;
    }
    
    int a1, b1;
    int g = exgcd(y, x%y, a1, b1);
    b = a1 + b1 * (x / y);
    a = b1;
    return g;
}

inline pii solve(const formula &a, const formula &b) {
    formula fx0 = a * b.c1 - b * a.c1;
    
    if (fx0.c2 == 0) {
        int ga, gb;
        int g = exgcd(a.c1, a.c2, ga, gb);
        return {ga * (-a.n1 / g), gb * (-a.n1 / g)};
    }
    
    int x2 = -fx0.n1 / fx0.c2;
    int x1 = (-a.n1 - a.c2 * x2) / a.c1;
    return {x1, x2};
}

const int maxn=1e4+100;
int t[maxn];
formula c[maxn];
int ci[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> t[i];
    }
    t[n+1] = t[1];
    t[n+2] = t[2];
    
    c[1] = {1, 0, 0};
    c[2] = {0, 1, 0};
    for (int i=3; i<=n+2; i++) {
        c[i] = formula{0, 0, t[i-1]} - c[i-1] - c[i-2];
//      cout << i << ' ' << c[i] << '\n';
    }
    
    pii ans = solve(c[n+1]-c[1], c[n+2]-c[2]);
    ci[1] = ans.first;
    ci[2] = ans.second;
    cout << ci[1] << '\n'
         << ci[2] << '\n';
    
    for (int i=3; i<=n; i++) {
        ci[i] = t[i-1] - ci[i-1] - ci[i-2];
        cout << ci[i] << '\n';
    }
    
    return 0;
}
```

## [P6255 [ICPC 2019 WF] Dead-End Detector](https://www.luogu.com.cn/problem/P6255)

一棵树的情况比较特殊，把每个叶子向相连的节点放一个标志。若不是树，可以参照拓扑排序，每次把“叶子”（度为 1 的点）砍掉，并且在一个节点被砍掉的时候撤销它的子胡同。

判断树的时候只需统计连通块的边数，统计 $\{(u, v) \in E \mid u<v\}$ 以去重。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+100;

int n, m;
vector<int> G[maxn];

int cocnt;
int con[maxn], com[maxn];
int vis[maxn];
int deg[maxn];

queue<int> q;
vector<int> sonht[maxn];

int from[maxn];

void dfs_co(int u) {
    vis[u] = true;
    con[cocnt]++;
    
    deg[u] = G[u].size();
    if (deg[u] == 1) {
        q.push(u);
    }
    
    for (int v: G[u]) {
        if (v < u) {
            com[cocnt]++;
        }
        
        if (!vis[v]) {
            dfs_co(v);
        }
    }
}

vector<pair<int, int>> ans;

void solve() {
    if (com[cocnt] == con[cocnt] - 1) {
        while (!q.empty()) {
            int leaf = q.front();
            q.pop();
            ans.push_back({leaf, G[leaf][0]});
        }
        return;
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int f: G[u]) {
            if (!from[f]) {
                from[u] = f;
            }
        }
        
        sonht[from[u]].push_back(u);
        
        deg[from[u]]--;
        if (deg[from[u]] == 1) {
            q.push(from[u]);
        }
        
        for (int son: sonht[u]) {
            from[son] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    for (int i=1; i<=n; i++) {
        if (!vis[i]) {
            cocnt++;
            dfs_co(i);
            solve();
        }
    }
    
    for (int i=1; i<=n; i++) {
        if (from[i]) {
            ans.push_back({from[i], i});
        }
    }
    
    sort(ans.begin(), ans.end());
    
    int u, v;
    cout << ans.size() << '\n';
    for (auto p: ans) {
        tie(u, v) = p;
        cout << u << ' ' << v << '\n';
    }
    
    return 0;
}
```