「codeforces - 1633F」Perfect Matching

本文主要是介绍「codeforces - 1633F」Perfect Matching，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

link。

首先所有的 activated nodes 组合成了一棵以 \(1\) 为根的有根树。询问即求由 activated nodes 组成的树的最大匹配。对于树上最大匹配有一个贪心策略：自底向上匹配当前点和其父亲，删除这两个点，直至只剩一个点或空树。若为空树，则树存在完美匹配。

Claim： 对于树 \(\textbf{T}=(\textbf{V},\textbf{E})\)，若存在完美匹配，当且仅当 \(\displaystyle\left(\sum_{u\in\textbf{V}}[|\text{subtree}(u)|\bmod2=1]\right)=\left(\sum_{u\in\textbf{V}}[|\text{subtree}(u)|\bmod2=0]\right)\)

Proof： 两个简单的观察即可证明：（1）每个子树大小为偶数的结点有且仅有一个子树大小为奇数的后继；（2）每个子树大小为奇数的结点的父亲子树大小为偶数。

所以偶数奇数两两对应，以上论断的充分性得证。其必要性的正确性比较平凡，故略。

然后我们需要支持的操作就只有加入一个叶子结点，反转一条无拐点的链上结点的标记。整棵树的形态是固定的，HLD 维护即可。具体方案的询问次数不超过 10 次，朴素 \(O(n)\) 寻找即可。

然而翻转链部分暴力也能过而且和线段树没啥本质区别……

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define cmin(x, y) x = std::min(x, y)
#define cmax(x, y) x = std::max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
int n, up[200100], all, on[200100], cnt, sz[200100], son[200100], top[200100], fa[200100], dfn[200100];
// params: @up[i]: identity of edge (i, fa[i]); @on[i]: is rev[i] activated; @all: amout of nodes activated;
//      @cnt: amout of odd nodes
std::vector<std::pair<int, int>> adj[200100];
std::set<int> S;
long long ans;
namespace hld {
    int tt;
    void dfs_sz(const int x, const int fa) {
        sz[x] = 1, ::fa[x] = fa;
        for(const auto [y, id] : adj[x]) if(y != fa) {
            dfs_sz(y, x);
            if(sz[y] > sz[son[x]]) son[x] = y;
        }
    }
    void dfs_hld(const int x, const int tp) {
        top[x] = tp, dfn[x] = ++tt;
        if(son[x]) dfs_hld(son[x], tp);
        for(const auto [y, id] : adj[x]) {
            if(y == fa[x]) up[dfn[x]] = id;
            if(y != fa[x] && y != son[x]) dfs_hld(y, y);
        }
    }
    void init() { dfs_sz(1, 0), dfs_hld(1, 1); }
}
signed main() {
    std::ios::sync_with_stdio(0);
    std::cin >> n;
    fors(i, 1, n-1, x, y) {
        std::cin >> x >> y;
        adj[x].emplace_back(y, i);
        adj[y].emplace_back(x, i);
    }
    on[1] = all = cnt = 1, hld::init();
    for(int op, x; "eternal love"; std::cout << "\n") {
        if(std::cin >> op, S.clear(); op == 1) {
            for(std::cin >> x, all++; x; x = fa[top[x]])
                fors(i, dfn[top[x]], dfn[x]) cnt += (on[i]?-1:1),ans += (on[i]?-1:1)*up[i],on[i] ^= 1;
            std::cout << ((all == cnt*2)?ans:0);
        } else if(op == 2) {
            if(all != cnt*2) std::cout << "0";
            else {
                fors(i, 2, n) if(on[i]) S.emplace(up[i]);
                std::cout << cnt;
                for(const int x : S) std::cout << " " << x;
            }
        } else break;
    }
    return 0;
}

这篇关于「codeforces - 1633F」Perfect Matching的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！