大致题意 :
对于一个树,有两种操作 :
1. 选择一个点x,删除所有与x相连的边和当前点 x
2. 选择一个点x,当前仅当x有两个连边到u - x和x - v的时候可以执行以下操作 :删除x点,并将u - x的边接向x - v,成为新边 u - v 。
问可以通过执行最少多少次1操作将所有点删除
输入格式
第一行一个整数 T($1 <= T <= 10^6$)表示测试数据数量,
每个测试数据的开始一个整数 n($1 <= n <= 10^6$),代表树的点数,
接下来跟着n - 1行每行两个数a,b表示树边($1 <= a,b <= n $)
输出格式
对于每组测试数据,在一行中输出一个整数表示最少的操作次数
思路
由题可知,我们是要尽可能的多做2操作。对于所有度数为1的节点其实我们可以看作他是一个叶子节点,而2操作其实可以看作一个路径的压缩。要压缩路径我们就得确保压缩中间的点只和两个边相连,所以我们可以得到一个结论 : 能做2操作的一定是树上的分支节点,从叶子节点u上层的父节点par开始看的话,如果要par能做2操作就得有par满足其只有两个边,对于多余的边得用1操作删掉。那么假设我们将所有par节点的多分支删成单分支,可以发现我们此时就可以对所有par节点做2操作了。如此往复,再将par当作叶子节点,可以发现我们每次其实都是在用原本的叶子节点去替代par节点,最后不断重复1操作然后2操作替换,最后可以得到我们的操作次数就是度数为1的节点数。这里需要特判下只有一个结点的情况(当时我写的时候就是因为没特判卡了很久,wa了很多发)
C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(a,b,c) for (register int a = b ; a < c ; ++a)
using namespace std;
typedef long long ll ;
typedef pair<int,int> pii ;
const int maxn = 1e6 + 10 ;
char c,num[15];bool f;int len;
template <typename T>
inline void R(T &x){
x = 0,f = 0,c = getchar();
while (c < '0' || c > '9' ){if (c == '-') f = 1;c = getchar();}
while (c >= '0'&& c <= '9' ){x = (x << 3) + (x << 1) + (c & 15) ; c = getchar() ;}
if (f) x = -x ;
}
template <typename T>
inline void W(T x) {
if (!x) putchar('0');
len = 0;
if (x < 0) putchar('-'), x = -x;
while(x) num[++len] = (x % 10) + 48, x /= 10;
while(len) putchar(num[len--]);
}
int out[maxn];
int main(){
int T,n = 0,u,v;
R(T);
while (T--){
R(n);
if (n == 1) {W(1),putchar('\n');continue ;}
rep(i,1,n + 1) out[i] = 0;
// 记得不要用memset,memset是O(n)的,如果T = 1e6,每次memset 也是1e6, 将会有1e12的复杂度,铁T,首先排除是我比赛用了memset还T了的
rep(i,1,n) R(u),R(v),++out[u],++out[v];
int res = 0;
rep(i,1,n + 1) res += out[i] == 1;
W(res),putchar('\n');
}
return 0;
}
样例不记得了,简单一点的就有
输入 :
2
1
1
2
1 2
输出
1
2