[计蒜客T2237]魔法_树
魔法
题目大意：
数据范围：
题解：
这个题挺好玩的
可以用反证法，发现所有叶子必须都得选而且所有叶子都选了合法。
故此我们就是要使得，一次操作之后使得叶子的个数最少。
这怎么弄呢？
我们发现，如果一条边相连的两个点$x$和$y$（$d_i$表示点$i$的度数，不妨设$d_x\le d_y$）满足：
$d_y\ge 3$且$d_x\ge 3$，那么叶子可以$-=2$。
如果$d_y\ge 3$且$d_x\le 2$，那么叶子可以$-=1$。
枚举每条边，看看最多能$-1$还是$-2$就好了~
代码：
#include <bits/stdc++.h>
#define N 200010
using namespace std;
int head[N], to[N << 1], nxt[N << 1], tot;
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
inline void add(int x, int y) {
to[ ++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
int d[N], x[N], y[N];
int main() {
int n = rd(), k = rd();
for (int i = 2; i <= n; i ++ ) {
x[i] = rd(), y[i] = rd();
d[x[i]] ++ ;
d[y[i]] ++ ;
}
int mx = 0;
for (int i = 2; i <= n; i ++ ) {
int s1 = d[x[i]], s2 = d[y[i]];
if (s1 < s2)
swap(s1, s2);
if (s1 >= 3) {
if (s2 >= 3) {
mx = max(mx, 2);
}
else if(s2 <= 2) {
mx = max(mx, 1);
}
}
}
int sum = 0;
for (int i = 1; i <= n; i ++ ) {
if (d[i] == 1) {
sum ++ ;
}
}
mx *= k;
cout << sum - mx << endl ;
return 0;
}
小结：有意思的题~
