题意简述：
给定一棵树，问有多少个节点满足：删去这个节点后的图的匹配数等于原树的匹配数。
( exttt{Data Range:} 2le nle 2 imes 10^5)。
首先你要知道一个结论：匹配数 = 节点数 - 最大独立集。
那么我们可以先通过一次树形 dp 求出原树的匹配数。即设 (f_{i,0/1}) 表示 (i) 子树中，(i) 不选 / 选的最大独立集大小。
考虑到删去一个点后，新图的最大独立集大小是其他联通块的最大独立集大小之和，而 (i) 儿子的子树内最大独立集大小已经在之前第一次树形 DP 时计算过，那么我们的目标就是要求出 (i) 子树外的最大独立集大小。
设 (g_{i,0/1}) 表示不考虑 (i) 子树，(i) 的父亲不选 / 选的最大独立集大小。
转移时，预先求出 (s0=sumlimits_{vin son_i}max{f_{v,0},f_{v,1}}) 和 (s1=sumlimits_{vin son_i}f_{v,0})，然后用 (g_{i,0/1}) 去转移 (g_{v,0/1})。
具体的，转移方程如下：
[egin{aligned}
g_{v,0} &= max(g_{i,0}, g_{i,1}) + s0 - max{f_{v,0}, f_{v,1}}\
g_{v,1} &= g_{i,0} + s1 - f_{v,0} + 1
end{aligned}
]
代码：
#include <bits/stdc++.h>
#define DC int T = gi <int> (); while (T--)
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> PII;
typedef pair <LL, int> PLI;
typedef pair <LL, LL> PLL;
template <typename T>
inline T gi()
{
T x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
template <typename T>
inline T abs(T x) {return x < 0 ? -x : x;}
const int N = 200003, M = N << 1;
int n;
int tot, head[N], ver[M], nxt[M];
int g[N][2], f[N][2];
inline void add(int u, int v) {ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;}
void dfs(int u, int fa)
{
f[u][1] = 1;
for (int i = head[u]; i; i = nxt[i])
{
int v = ver[i];
if (v == fa) continue;
dfs(v, u);
f[u][0] += max(f[v][0], f[v][1]), f[u][1] += f[v][0];
}
}
void dfs1(int u, int fa)
{
int s0 = 0, s1 = 0;
for (int i = head[u]; i; i = nxt[i])
{
int v = ver[i];
if (v == fa) continue;
s0 += max(f[v][0], f[v][1]), s1 += f[v][0];
}
for (int i = head[u]; i; i = nxt[i])
{
int v = ver[i];
if (v == fa) continue;
g[v][0] = max(g[u][0], g[u][1]) + (s0 - max(f[v][0], f[v][1]));
g[v][1] = g[u][0] + s1 - f[v][0] + 1;
dfs1(v, u);
}
}
int main()
{
//freopen(".in", "r", stdin); freopen(".out", "w", stdout);
n = gi <int> ();
for (int i = 1; i < n; i+=1)
{
int u = gi <int> (), v = gi <int> ();
add(u, v), add(v, u);
}
dfs(1, 0);
int ans = n - max(f[1][0], f[1][1]), cnt = 0;
dfs1(1, 0);
for (int i = 1; i <= n; i+=1)
{
int bs = n - 1;
int now = f[i][0] + max(g[i][0], g[i][1]);
if (bs - now == ans) ++cnt;
}
printf("%d
", cnt);
return !!0;
}