Cut 'em all! CodeForces - 982C（贪心dfs）

太过爱你忘了你带给我的痛 2021-12-16 12:35 160阅读 0赞

# #

## [K - Cut 'em all!][K - Cut _em all] ##

[CodeForces - 982C][]

给一棵树 求最多能切几条边使剩下的子树都有偶数个节点

如果n是奇数 那么奇数=偶数+奇数 不管怎么切 都会有奇数

直接打印-1

贪心 如果子树中的点是偶数 就可以直接切了

最后答案要减一 因为原来的树也是偶数个节点 会被统计进去

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    const int maxn = 1e5 + 10;
    int res[maxn];
    bool vis[maxn];
    int ans;
    vector<int> G[maxn];
    
    void dfs(int u) {
        vis[u] = true;
        res[u] = 1;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (vis[v]) continue;
            dfs(v);
            res[u] += res[v];
        }
        if (res[u] & 1) return;
        res[u] = 0;
        ans++;
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        for (int i = 0, u, v; i < n - 1; i++) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        if (n & 1) {
            puts("-1");
            return 0;
        }
        dfs(1);
        printf("%d\n", ans-1);
        return 0;
    }

转载于:https://www.cnblogs.com/Mrzdtz220/p/10514381.html

[K - Cut _em all]: https://vjudge.net/problem/CodeForces-982C
[CodeForces - 982C]: https://vjudge.net/problem/1576783/origin
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/efd1c333d0d24ded8801d60e624a192b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 codeforces 603 C. Load Balancing 贪心

C. Load Balancing time limit per test 2 seconds memory limit per test 256 megabytes

清疚/ 2022年08月18日 15:22/ 0 赞/ 48 阅读

相关 codeforces C. Bits 贪心

C. Bits time limit per test 1 second memory limit per test 256 megabytes input sta

偏执的太偏执、/ 2022年07月24日 09:16/ 0 赞/ 179 阅读

相关 codeforces C. Money Transfers 贪心

C. Money Transfers time limit per test 1 second memory limit per test 256 megabytes

怼烎@/ 2022年07月24日 08:14/ 0 赞/ 167 阅读

相关 C - Hot Bath CodeForces - 127C——贪心

Think: 1>题意：已知冷水温度t1,热水温度t2,冷水最高释放速度x1,热水最高释放速度x2,问如何控制释放速度可使最快达到正趋向于温水温度t0 1>题意建模：两

矫情吗；*/ 2022年06月14日 02:12/ 0 赞/ 137 阅读

相关 CodeForces 873C(贪心)

问题描述: Ivan is playing a strange game. He has a matrix a with n rows and m columns. Eac

深藏阁楼爱情的钟/ 2022年06月07日 12:49/ 0 赞/ 122 阅读

相关 CodeForces 825C(贪心)

问题描述: Makes solves problems on Decoforces and lots of other different online judges. Ea

r囧r小猫/ 2022年06月06日 13:00/ 0 赞/ 138 阅读

相关 Codeforces 193A. Cutting Figure（dfs）

You've gotten an n × m sheet of squared paper. Some of its squares are painted. Let's ma

阳光穿透心脏的1/2处/ 2022年06月02日 03:59/ 0 赞/ 87 阅读

相关 Cut 'em all! CodeForces - 982C（贪心dfs）

[K - Cut 'em all!][K - Cut _em all] [CodeForces - 982C][] 给一棵树求最多能切几条边使剩下的子树都有偶

太过爱你忘了你带给我的痛/ 2021年12月16日 12:35/ 0 赞/ 161 阅读

相关 CodeForces - 218C : Ice Skating（DFS）

Discription Bajtek is learning to skate on ice. He’s a beginner, so his only mode of t

比眉伴天荒/ 2021年11月26日 22:02/ 0 赞/ 188 阅读

相关 Elections CodeForces - 1020C (贪心)

大意: 有n个选民, m个党派, 第i个选民初始投$p\_i$一票, 可以花费$c\_i$改变投票, 求最少花费使得第一个党派的票数严格最大假设最终第一个党派得票数$

淩亂°似流年/ 2021年10月01日 00:20/ 0 赞/ 242 阅读