Znzryb's Blog
0%

CF-1000-C. Remove Exactly Two

Posted on Edited on

思路讲解

其实还是挺简单的，不难，就是要分类讨论一下

前面搞着搞着搞错了，其实cnt→fi才是我们要加的

就是如果说我们不知道怎么排序或者什么，我们可以直接将答案算出来，取最大的答案就行了

1
2
3
4
5
6
7
8
9
10
11
12
lans -= 1;  // 先不管我们这个要做第二个操作的联通块
if (cnt.rbegin()->fi > 1) {
  // #ifdef LOCAL
  // cerr << lans << '\n';
  // #endif
  lans += cnt.rbegin()->fi;
} else if (cnt.rbegin()->fi == 1) {
  // #ifdef LOCAL
  // cerr<<"In if:" << i << ' ' << lans << '\n';
  // #endif
  lans += cnt.rbegin()->fi - 1;
}

AC代码

AC

https://codeforces.com/contest/2063/submission/305604041

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// Problem: C. Remove Exactly Two
// Contest: Codeforces - Codeforces Round 1000 (Div. 2)
// URL: https://codeforces.com/contest/2063/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T;
vector<ll> g[MAXN];
ll edges[MAXN];

inline void solve() {
  cin >> N;
  map<ll, ll> cnt;
  // 初始化
  FOR(i, 1, N) { g[i].clear(); }
  FOR(i, 1, N - 1) {
    ll u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  if (N == 2) {
    cout << 0 << '\n';
    return;
  }
  ll mx = 0, mxN = 1;
  FOR(i, 1, N) {
    edges[i] = SZ(g[i]);
    cnt[edges[i]] = cnt.find(edges[i]) == cnt.end() ? 1 : cnt[edges[i]] + 1;
  }
  ll ans = 0;
  map<ll, ll> backup = cnt;
  FOR(i, 1, N) {
    ll lans = edges[i];
    // #ifdef LOCAL
    // cerr << i << ' ' << edges[i] << '\n';
    // #endif
    cnt[edges[i]] -= 1;
    if (cnt[edges[i]] == 0) {
      cnt.erase(edges[i]);
    }
    FOR(j, 0, SZ(g[i]) - 1) {
      ll node = g[i][j];
      cnt[edges[node]] -= 1;
      cnt[edges[node] - 1] = cnt.find(edges[node] - 1) == cnt.end() ? 1 : cnt[edges[node] - 1] + 1;
      if (cnt[edges[node]] == 0) {
        cnt.erase(edges[node]);
      }
    }
    lans -= 1;  // 先不管我们这个要做第二个操作的联通块
    if (cnt.rbegin()->fi > 1) {
      // #ifdef LOCAL
      // cerr << lans << '\n';
      // #endif
      lans += cnt.rbegin()->fi;
    } else if (cnt.rbegin()->fi == 1) {
      // #ifdef LOCAL
      // cerr<<"In if:" << i << ' ' << lans << '\n';
      // #endif
      lans += cnt.rbegin()->fi - 1;
    }

    // #ifdef LOCAL
    // cerr << i << ' ' << lans << '\n';
    // #endif
    ans = max(ans, lans);
    cnt = backup;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
#ifdef LOCAL
    cerr << '\n';
#endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2063/submission/305604041
1
5
1 2
1 3
2 4
3 5

3

1
3
1 2
1 3

1
*/

心路历程（WA，TLE，MLE……）