一些关键的提示 & 性质：

• \(n\) 为奇数，只有一个重心 \(\to\) 不用考虑奇奇怪怪的 corner case。

• 链的部分分启发我们去考虑树链剖分。

• 二叉树的部分分启发我们去考虑以重心为根的情况。

两种可能性：

• 枚举 \(u\) 计算它作为重心的次数 \(\to\) 偏向数据结构的技巧。
• 枚举 \((u, v)\) 迅速寻找两个重心 \(\to\) 偏向树论的技巧。

\(\forall u\)，想知道它会成为几次重心。

以 \(u\) 为根讨论，设其最大子树为 \(son\)，大小为 \(w\)，次大子树大小为 \(s\)。

• \(v\in \text{tree}(son)\)，要满足 \(2w - n\le siz_v\le n - 2t\)。
• \(v\ne \text{tree}(son)\)，要满足 \(siz_v \le n - 2S\)。

这是一个二维数点，注意讨论 “儿子是父亲” 的情况。

考虑删边迅速求重心。

重心的性质：

• 距离和最小：树中所有点到重心的距离和是最小（可能且最多有两个）的，反过来也可以用这个求重心。
• 子树大小限制：所有两倍子树大小 \(\le n\)，最大的子树大小最小。
• 数量性质：一棵树最多两个重心，且相邻，节点个数为奇数则最多一个重心。
• 重心移动：一棵树添加或删除一个节点，重心最多只移动一条边的位置。
• 两重心连线：把两棵树通过某条边相连，新的重心一定在两棵树原重心连线上。
• 重心与重链：重心在从根开始的重链上。

考虑倍增跳重儿子，这样可以 \(\mathcal{O}(\log n)\) 求出一个子树的重心。

现在需要考虑 “向上跳”，可以考虑类似 “换根 dp” 的方法。

换根的时候，维护正确的 \(son_u\) 数组，和倍增数组，然后求出所有儿子的子树的重心贡献到答案里。

咱继续想象，以重心为根会有怎样的效果呢？

先求出以重心为根后，所有子树的重心：

• 重子树的重心往上跳。
• \(\mathcal{O}(n)\)。

开始讨论：

• 如果删掉的边不在重子树内：

  • 在重子树里面跳。
  • 这部分可以 \(\mathcal{O}(n)\) 预处理（固定外面删掉的子树的大小）。

• 如果删掉的边在重子树内。

  • 如果重子树仍然为重子树：根还是重心。
  • 否则类似上面还是可以预处理（次重儿子里面跳）。

所以只要求 \(g\) 就可以，可以利用组合意义直接得出式子。

Source

cpp

如果知道了区间所有数的出现次数，暴力查询的时间复杂度是 \(\mathcal{O}(\sqrt {n})\) 的，于是考虑维护区间的出现次数的桶，带修莫队即可。

#include <bits/extc++.h>

using i64 = long long;

using std::cin;
using std::cout;
using std::vector;

constexpr int N = 2E5 +10;

int idx = 0;
std::map<int, int> mp;
int get(int x) {
    if (!mp[x]) mp[x] = ++idx;
    return mp[x];
}

int bl[N];
struct Q {
    int id;
    int l, r, t;
    bool operator <(Q a) const {
        return bl[l] == bl[a.l] ? (bl[r] == bl[a.r] ? t < a.t : r < a.r) : l < a.l;
    }
}q[N]; int tq = 0;

struct  O {
    int p, x, y;
}o[N]; int t = 0;

int f[N], c[N];
void add(int x) {
    --f[c[x]];
    ++f[++c[x]];
}
void del(int x) {
    --f[c[x]];
    ++f[--c[x]];
}

int a[N];
int ans[N];
int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        a[i] = get(x);
        bl[i] = i / 2137;
    }
    
    for (int op, x, y; m--; ) {
        cin >> op >> x >> y;
        if (op == 1) {
            ++tq, q[tq] = {tq, x, y, t};
        } else {
            ++t, o[t] = {x, get(y), a[x]};
            a[x] = o[t].x;
        }
    }
    
    std::sort(q + 1, q + tq + 1);
    
    for (int i = 1, l = 1, r = 0; i <= tq; i++) {
        for (; t > q[i].t; t--) {
            a[o[t].p] = o[t].y;
            if (l <= o[t].p && o[t].p <= r) {
                add(o[t].y);
                del(o[t].x);
            }
        }
        for (; t < q[i].t; ) {
            ++t;
            a[o[t].p] = o[t].x;
            if (l <= o[t].p && o[t].p <= r) {
                add(o[t].x);
                del(o[t].y);
            }
        }

        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        
        int j = 1;
        while (f[j]) ++j;
        ans[q[i].id] = j;
    }

    for (int i = 1; i <= tq; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

不用脑子的建虚树：

• 排序，加 \(\text{LCA}\)，排序，\(\text{LCA}(o_i, o_{i - 1})\) 向 \(o_i\) 连边。
• \(o_0\) 为根。
• 记得初始化。

相比普通的最长上升子序列，需要多记录末尾的数：\(f_{i, j}\) 钦定 LCIS 的末尾是 \(b_j\) 即可。

这个自动机上的节点有两个描述的指标，将 \(i\) 作为主元，只会从 \(i - 1\) 跳到 \(i\)，会使我的代码逻辑清晰。

输出方案要么直接记录，要么通过 dp 值推往哪走。

容易联想到欧拉回路，（无向图）存在欧拉回路的充要条件是所有点的度数都是的偶数。

所以先将奇度数的点两两配对连边（任意配对，奇度数的点一定是偶数个，度的和为偶数），使原图存在欧拉回路。

先草率的定个向，跑一边欧拉回路，相邻的两条边 \((u, v),(v, w)\) 定向为 \(v\to u, v\to w\)，还是两两配对。

所以完备的做法就是如果无法两两配对，加个自环。

#include <bits/extc++.h>

using i64 = long long;

using std::cin;
using std::cout;
using std::vector;

constexpr int N = 8E5 + 5;

int deg[N];
int num = 1, fir[N], nxt[N], to[N];
void add(int u, int v) {
    to[++num] = v, nxt[num] = fir[u], fir[u] = num;
}
void addEdge(int u, int v) {
    add(u, v);
    add(v, u);
    deg[u]++;
    deg[v]++;
}

int idx;
bool vis[N];
void dfs(int u) {
    for (int &i = fir[u]; i; i = nxt[i]) {
        if (vis[i]) continue;
        vis[i] = vis[i ^ 1] = 1;
        int v = to[i];
        dfs(v);
        if ((++idx) & 1) {
            cout << u << ' ' << v << '\n';
        } else  {
            cout << v << ' ' << u << '\n';
        }
    }
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }   
    
    int u = -1;
    for (int i = 1; i <= n; i++) {
        if (deg[i] & 1) {
            if (u == -1) {
                u = i;
            } else {
                addEdge(u, i);
                ++m;
                u = -1;
            }
        }
    }

    if (m & 1) {
        addEdge(1, 1);
        ++m;
    }

    cout << m << '\n';
    dfs(1);
    return 0;
}

直觉上，把所有限制化作相同形式会好处理得多：\(1 \le i - a_i \le n\)。

于是将 \(\sum a_i = 0\) 的条件转化为了 \(\sum (i - a_i) = \sum i\)。

强化这个条件（“构造题方法总汇”），让每个 \(i - a_i\) 对应一个 \(i\)，连边，找基环树的环。

#include <bits/extc++.h>

using std::cin;
using std::cout;
using std::vector;
using i64 = long long;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    vector<int> to(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        to[i] = i - a[i];
    }

    int u = 1;
    while (n--) {
        u = to[u];
    }

    vector<int> ans;
    ans.push_back(u);
    while (to[u] != ans[0]) {
        u = to[u];
        ans.push_back(u);
    }

    cout << ans.size() << '\n';
    for (auto x : ans) cout << x << ' ';
    cout << '\n';
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}

全选撤销贪心。

容斥原理容易列出式子：

\(f(i, j)\) 表示钦定了 \(i\) 行同色，\(j\) 列同色的方案数。

情况一（竟然推漏了）：\(ij = 0\)。

所以对最终答案的贡献容易写出：

情况二：\(ij\ne 0\)。

开始推式子：

考虑很快的计算里面的 \(\sum\)。

根据二项式定理 \((a + b)^n = \sum\limits_{i = \color{red} 0}^n \binom{n}{i}a^ib^{n - i}\)。

反悔贪心。

• 选一。
• 一升二。
• 退一选二。
• 退二选二。

四个堆。

直接贪心。

最朴素的错误贪心是堆维护：

• 选一。
• 选二。

这样如果 \(a_i\) 很大，\(b_i - a_i\) 都很小就会错得离谱。

所以魔改一下，权衡一下选两星还是一星：

• 维护 \(a_i\) 小根堆。
• \(b_i\) 的小根堆。

如果可以选两个，且 \(b_i\) 更优，就选 \(b_i\)，记得清楚 \(a_i\) 堆里使用过的元素。

按 \(b_i\) 排序。

假设 \(i\) 是最大的选了两颗星的编号。

\(1\sim i\) 肯定都选了 \(\ge 1\) 颗星。

\(i + 1\sim n\) 最多只选一颗星。

需要一个维护前 \(k\) 大的和的数据结构。

线段树上二分即可。

别搅动浑水。

你的灵魂会澄清。

你的渣滓会沉淀。

你的痛苦会治好。

正难则反，先把相交的回文串，变成不交的，这里需要计算出回文串个数。

考虑扫描线，将结尾位置相同的回文串放在一起考虑，那后面的所有回文串都会计入贡献。

于是只要维护以 \(i\) 开头和结尾的回文串个数就行。manacher 和 PAM 都可以。

先将所有路径按长度排序（大到小）。

最终肯定是使一段前缀减去一条边的权值，一段后缀保留（可能为空）。

二分保留哪一段后缀即可。

现在需要 check 能否让前缀所有路径都 \(\le\) 某一个数，首先所有前缀路径都得经过，其次得最大，树上差分做完了。

如果本身是二分图，那么任意删去一条边皆可。

否则拉出 dfs 树讨论，一次要删除所有奇环，树上差分。

当取得阶段性的胜利时。

要驻足思考：

• 代码流程是什么样的。
• 繁杂的流程能否缩减。
• 这道题就是很好的例子。

二分转化为判定性问题。

• 如果一个点走不到根。
  • 一定走到能走到的最浅的点。
  • 将所有这些点 \(\text{mark}\) 标记为 \(1\)。
  • 第一遍维护每个点的深度。
  • dfs 维护到每个点最浅的 \(\text{mark}\) 的深度差。
    • 如果深度差 \(\le mid\)。
    • 或 \(flag = 1\)。
      • \(flag\) 表示所有儿子都被控制。
    • 那么这个点也被控制。
• 如果一个点能走到根。
  • 先放入 \(\text{rest}\) 集合。
    • 维护 \(\text{bel}\) 表示属于根的哪个儿子。
    • 先将所有能到根的点存入 \(\text{rest}(\text{bel})\)。
    • 这一步是关键：对于每个 \(\text{rest}(\text{bel})\) 里剩余最小的点，判断它是否只有匹配自己是优秀的：如果到根剩余路程到不了自己的 \(\text{bel}\)，那么给自己肯定是最优的。
  • 最后将所有 \(\text{rest}\) 合并成一个大的。
  • 维护 \(\text{need}\) 集合表示没有被完全控制的根的儿子。
  • \(\text{need}\) 和 \(\text{rest}\) 都排序，一一对应。

#include <bits/extc++.h>

using i64 = long long;

constexpr i64 inf = 4E17;

using std::cin;
using std::cout;
using std::vector;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    cin >> n;
    
    vector<vector<std::pair<int, i64>>> adj(n); 
    for (int i = 1; i < n; i++) {
        int u, v;
        i64 w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    int rt;
    bool flag;
    vector<i64> dep(n), ndep(n), bel(n);
    auto predfs = [&](auto self, int u, int p) -> void {
        if (adj[u].size() != 2 && !flag) {
            flag = 1;
            ndep[rt] = dep[u];
        }
        bel[u] = rt;
        for (auto [v, w] : adj[u]) {
            if (v == p) continue;
            dep[v] = dep[u] + w;
            self(self, v, u);
        }
    };
    vector<int> son;
    for (auto [u, w] : adj[0]) {
        flag = 0;
        rt = u;
        dep[u] = w;
        predfs(predfs, u, 0);
        son.push_back(u);
    }

    int q;
    cin >> q;
    if (q < son.size()) {
        cout << "-1";
        return 0;
    }
    
    vector<int> o(q);
    for (int i = 0; i < q; i++) {
        cin >> o[i];
        --o[i];
    }

    auto check = [&](int m) -> bool {
        vector<bool> mark(n, 0);
        vector<bool> mk(n, 0);
        vector<i64> dp(n, inf);
        for (auto i : o) {
            if (dep[i] >= m) {
                mark[i] = 1;
            }
        }

        auto dfs = [&](auto self, int u, int p) -> void {
            bool is = adj[u].size() != 1;
            if (mark[u]) dp[u] = 0;
            for (auto [v, w] : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
                dp[u] = std::min(dp[u], dp[v] + w);
                is = is & mk[v];
            }
            mk[u] = is | dp[u] <= m;
        };
        dfs(dfs, 0, -1);


        vector<std::vector<i64>> rest(n);
        for (auto i : o) {
            if (dep[i] < m) {
                rest[bel[i]].push_back(m - dep[i]);
            }
        }

        for (auto x : son) {
            std::sort(rest[x].begin(), rest[x].end(), std::greater<i64>());
            if (!mk[x] && !rest[x].empty() && *rest[x].rbegin() <= dep[x]) {
                rest[x].pop_back();
                mk[x] = 1;
            }
        }

        vector<i64> nrest;
        vector<i64> need;
        for (auto x : son) {
            if (!mk[x]) need.push_back(dep[x]);
            for (auto x : rest[x]) {
                nrest.push_back(x);
            }
        }

        std::sort(need.begin(), need.end());
        std::sort(nrest.begin(), nrest.end());
        
        int j = 0;
        for (int i = 0; i < need.size(); i++) {
            while (j < nrest.size() && nrest[j] < need[i]) ++j;
            if (j == nrest.size()) return 0;
            ++j;
        }
        return 1;
    };

    i64 L = 0, R = inf, ans = R;
    while (L <= R) {
        int m = (L + R) / 2;
        if (check(m)) {
            ans = m, R = m - 1;
        } else {
            L = m + 1;
        }
    }

    cout << ans;
    return 0;
}    

结论题还是太深刻了。

 答案 \(\le n\)，更紧一点是奇数个数 

所以可以感受到其实变化不多。

 至少有一半是数 \(\Delta\le 1\) 

因为答案 \(\le n\)，\(\Delta>2\) 就不可能超过一半。

所以在时间允许的范围内随机撒点命中它们。

#include <bits/extc++.h>

using i64 = long long;

using std::cin;
using std::cout;
using std::vector;

std::mt19937 rnd(std::random_device{}());

vector<int> minp;
vector<i64> primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    cin >> n;

    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sieve(1000000);

    vector<i64> o;
    std::shuffle(a.begin(), a.end(), rnd);
    auto insert = [&](i64 x) {
        if (x == 0 || x == 1) return;
        for (auto p : primes) {
            if (x % p == 0) {
                while (x % p == 0) {
                    x /= p;
                }
                o.push_back(p);
            }
        }
        if (x > 1) o.push_back(x);
    };

    for (int i = 0; i < std::min(n, 50); i++) {
        insert(a[i]);
        insert(a[i] + 1);
        insert(a[i] - 1);
    }

    i64 ans = n;
    for (auto p : o) {
        i64 tot = 0;
        for (int i = 0; i < n; i++) {
            i64 x = a[i] % p;
            if (a[i] - x != 0) tot += std::min(x, p - x);
            else tot += p - x;
        }
        ans = std::min(ans, tot);
    }
    cout << ans;
    return 0;
}

具体的树不重要，按照 dfs 序顺序排列叶子，\(w_i\) 对应这一段区间，区间加，差分一下。

有 \(n\) 区间，选择一个区间需要 \(w_i\) 的代价，可以对选择的区间任意执行区间加操作（差分 \(a_{l} + k, a_{r + 1} - k\)），求最少的代价，可以任意执行单点加操作。

这种难以解决的全局限制直接考虑图论好吧。

最小生成树。

先求 \((w, u, v, id)\)：

• dfs 时记录遇到的叶子数。
• \([in, out] = [l, r]\)。

代码很好写。

#include <bits/extc++.h>

using i64 = long long;

using std::cin;
using std::cout;
using std::vector;

struct Edge {
    int w, u, v, id;
};

struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return 0;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        f[y] = x;
        siz[x] += siz[y];
        return 1;
    }
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    std::cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int cur = 0;
    vector<Edge> eg;
    auto dfs = [&](auto self, int u, int p) -> void {
        int w = a[u], l = cur, r, id = u;
        for (auto v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
        }
        if (adj[u].size() == 1 && u) cur++;
        r = cur;
        eg.push_back((Edge){w, l, r, id});
    };
    dfs(dfs, 0, -1);

    i64 ans = 0;
    vector<int> ansid;
    DSU dsu(n);

    std::sort(eg.begin(), eg.end(), [&](Edge a, Edge b) {return a.w < b. w;});

    int m = eg.size(), cnt = 0;
    for (int i = 0, l, r; i < m; i++) {
        l = r = i;
        while (r < m && eg[r + 1].w == eg[r].w) ++r;
        for (int j = l; j <= r; j++) {
            int u = dsu.find(eg[j].u), v = dsu.find(eg[j].v);
            if (u != v) {
                ansid.push_back(eg[j].id);
            }
        }
        
        for (int j = l; j <= r; j++) {
            int u = dsu.find(eg[j].u), v = dsu.find(eg[j].v);
            if (u == v) continue;
            ans = ans + eg[j].w;
            dsu.merge(u, v);
            ++cnt;
        }
        if (cnt == cur) break;
        i = r;
    }

    cout << ans << ' ' << ansid.size() << '\n';

    std::sort(ansid.begin(), ansid.end());
    for (auto x : ansid) cout << x + 1 << ' ';
    return 0;
}

• \(\texttt{Trap 1}\)：可能在最小生成树中的边，相同边权一起考虑，如果只考虑 \(<w\) 时，\((u, v)\) 还不连通，就有可能在最终生成树中。
• \(\texttt{Trap 2}\)：移动下标指针 ++r 时，不要忘了写上界，不能只有性质限制条件。
• \(\texttt{Trap 3}\)：不要忘了写 i = r。

枚举 \(x = 1\sim 9\) 计算贡献。

数位 dp 板子状态，\(f(i, 0/1)\) 表示只考虑前 \(i\) 位（高到低考虑），顶不顶上界的答案。

• 如果填的数 \(\ge x\)：\(f(i)\leftarrow_+ f(i - 1)\)。
• 如果填的数 \(= x\)：\(f(i)\leftarrow_+ f(i - 1)\times 10 + g(i - 1)\)。
• 如果填的数 \(\le x\)：\(f(i)\leftarrow_+ f(i - 1)\times 10\)。

\(g(i, 0/1)\) 就表示，下一位填 \(=x\)，这个 \(x\) 会产生的贡献。

• 填数 \(g(i)\)
  • 填的数 \(\le x\)：\(g(i)\leftarrow_+ g(i - 1)\)
  • 填的数 \(> x\)：\(g(i)\leftarrow_+ 10g(i - 1)\)

#include <bits/extc++.h>

using i64 = long long;

constexpr int P = 1E9 + 7;

using std::cin;
using std::cout;
using std::vector;

void Inc(int &x, int y) {
    if ((x += y) >= P) x -= P;
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    std::string s;
    cin >> s;

    int n = s.size();

    int d;
    int ans = 0;

    auto work = [&]() {
        vector<std::array<int, 2>> f(n + 1), g(n + 1);
        g[0][1] = d;
        for (int i = 0; i < n; i++) {
            int x = s[i] - '0';
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 10; k++) {
                    if (j && k > x) {
                        break;
                    }
                    int o = (j && k == x);
                    if (k < d) {
                        Inc(f[i + 1][o], f[i][j]);
                        Inc(g[i + 1][o], g[i][j]);
                    } else if (k == d) {
                        Inc(f[i + 1][o], 10ll * f[i][j] % P);
                        Inc(f[i + 1][o], g[i][j]);
                        Inc(g[i + 1][o], g[i][j]);
                    } else if (k > d) {
                        Inc(f[i + 1][o], 10ll * f[i][j] % P);
                        Inc(g[i + 1][o], 10ll * g[i][j] % P);
                    }
                }
            }
        }
        Inc(ans, f[n][0]);
        Inc(ans, f[n][1]);
    };


    for (d = 1; d < 10; d++) {
        work();
    }

    cout << ans;
    return 0;
}

• \(\texttt{Trap 1}\)：分清楚数字 d 和你要填的 x。

shaber 题。

#### [$\color{violet}{\texttt{题目名称}}$](题目链接)

<details>
  <summary>$\texttt{Solution}$</summary>



</details>

<details>
  <summary>$\texttt{Code}$</summary>

```cpp```


</details>

<details>
  <summary>$\texttt{Trap}$</summary>
- $\texttt{Trap 1}$：。


</details>

#### [$\color{lightblue}{\texttt{题目名称}}$](题目链接)

<details>
  <summary>$\texttt{Solution}$</summary>

</details>

<strong style="color: green">结论写这里</strong>

<strong style="color: pink">结论写这里</strong>

<strong style="color: red">警告</strong>