Codeforces Round #798 C. Infected Tree

Byteland is a beautiful land known because of its beautiful trees.

Misha has found a binary tree with nn vertices, numbered from 11 to nn. A binary tree is an acyclic connected bidirectional graph containing nn vertices and n−1n−1 edges. Each vertex has a degree at most 33, whereas the root is the vertex with the number 11 and it has a degree at most 22.

Unfortunately, the root got infected.

The following process happens nn times:

• Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.
• Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).

As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).

Input

There are several test cases in the input data. The first line contains a single integer tt (1≤t≤50001≤t≤5000) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer nn (2≤n≤3⋅1052≤n≤3⋅105) — the number of vertices of the tree.

The ii-th of the following n−1n−1 lines in the test case contains two positive integers uiui and vivi (1≤ui,vi≤n1≤ui,vi≤n), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at 11. It is also guaranteed that the sum of nn over all test cases won't exceed 3⋅1053⋅105.

Output

For each test case, output the maximum number of vertices Misha can save.

Example

input

Copy

4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15

output

Copy

0
2
2
10

Note

In the first test case, the only possible action is to delete vertex 22, after which we save 00 vertices in total.

In the second test case, if we delete vertex 22, we can save vertices 33 and 44.

 这一题的思路一个佬的博客讲的非常清晰我超越不了直接贴上顺便膜个佬

Infected Tree - cbmango - 博客园

贴贴我自己写的代码吧~（虽然跟佬写的差不多

#include
#include
#include
#include

using namespace std;
const int N=300005;
int n;
int f[N];
int cnt[N];
vector v[2*N];
void dfs1(int u,int father){
	cnt[u]=1;
	for(int i=0;i>n;
	for(int i=1;i<=n;i++){
		v[i].clear();
		f[i]=0;
		cnt[i]=0;
	}
	for(int i=1;i>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs1(1,-1);
	dfs2(1,-1);
	printf("%dn",f[1]);
}
int main(){
	int t;
	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}