设 \(f_{u,0/1}\) 为 \(u\) 的子树，\(u\) 是否在匹配内的最大匹配数。
注意到对于一个匹配，在它深度较浅的点上才会被计入答案。
转移大概是 \(f_{u,0}\) 取 \(\sum\limits_{v \in son_u} \max(f_{v,0}, f_{v,1})\)，\(f_{u,1}\) 要从儿子中选一个 \(f_{v,0}\)，剩下的选 \(\max(f_{v,0}, f_{v,1})\)。先假设全部选 \(\max(f_{v,0}, f_{v,1})\)，求出 \(\max\limits_{v \in son_u} f_{v,0} - \max(f_{v,0}, f_{v,1})\)，加进 \(f_{u,1}\) 即可。
发现还要求以父亲为根的子树的最大匹配，这个是换根基础操作，转移式同上。减去儿子的 \(\max\) 部分，维护前缀 \(\max\) 和后缀 \(\max\) 即可。注意特殊处理根。
code
// Problem: G - Vertex Deletion
// Contest: AtCoder - AtCoder Beginner Contest 223
// URL: https://atcoder.jp/contests/abc223/tasks/abc223_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int inf = 0x3f3f3f3f;
int n, head[maxn], len, ans, f[maxn][2], g[maxn][2];
struct edge {
int to, next;
} edges[maxn << 1];
inline void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
void dfs(int u, int fa) {
int d = -inf;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == fa) {
continue;
}
dfs(v, u);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += max(f[v][0], f[v][1]);
d = max(d, f[v][0] - max(f[v][0], f[v][1]));
}
f[u][1] += d + 1;
}
void dfs2(int u, int fa, int f0, int f1) {
int nf0 = f0, nf1 = f1;
vector<int> son(1, 0);
int k = max(f0, f1);
f0 = f1 = max(f0, f1);
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == fa) {
continue;
}
son.pb(v);
k += max(f[v][0], f[v][1]);
f0 += max(f[v][0], f[v][1]);
f1 += max(f[v][0], f[v][1]);
}
if (k == max(f[1][0], f[1][1])) {
++ans;
}
int cnt = (int)son.size() - 1;
vector<int> pre(cnt + 2), suf(cnt + 2);
pre[0] = suf[cnt + 1] = (u == 1 ? -inf : nf0 - max(nf0, nf1));
for (int i = 1; i <= cnt; ++i) {
int v = son[i];
pre[i] = max(pre[i - 1], f[v][0] - max(f[v][0], f[v][1]));
}
for (int i = cnt; i; --i) {
int v = son[i];
suf[i] = max(suf[i + 1], f[v][0] - max(f[v][0], f[v][1]));
}
for (int i = 1; i <= cnt; ++i) {
int v = son[i];
if (u == 1 && cnt == 1) {
dfs2(v, u, 0, -inf);
} else {
dfs2(v, u, f0 - max(f[v][0], f[v][1]), f1 - max(f[v][0], f[v][1]) + max(pre[i - 1], suf[i + 1]) + 1);
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs(1, -1);
dfs2(1, -1, 0, -inf);
// printf("%d\n", max(f[1][0], f[1][1]));
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}