题目：Infected Tree
Byteland is a beautiful land known because of its beautiful trees.
Misha has found a binary tree with n vertices, numbered from 1 to n. A binary tree is an acyclic connected bidirectional graph containing n vertices and n−1 edges. Each vertex has a degree at most 3, whereas the root is the vertex with the number 1 and it has a degree at most 2.
Unfortunately, the root got infected.
The following process happens n 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 t (1≤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 n (2≤n≤3⋅105) — the number of vertices of the tree.
The i-th of the following n−1 lines in the test case contains two positive integers ui and vi (1≤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 1. It is also guaranteed that the sum of n over all test cases won’t exceed 3⋅105.
Output
For each test case, output the maximum number of vertices Misha can save.
Example
input
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
大意：二叉树的根部被感染，每次都可以选择一个子节点切除这个子节点的所有边，这个节点的所有子节点即被拯救，问最多能拯救多少个子节点。
我们不难发现，对于每个除了根节点的节点只有两个选择，即作为被选中切边的节点或者被拯救的节点，由于题目所求是拯救节点的最大值，这样根据状态求答案的情况我们很容易便可以想到dp，加上总体框是一个二叉树，那么自然便是树形dp了。
想到树形dp之后，我们又该如何构造状态转移方程呢？首先，由于受到感染是一层一层传递的，那么我们就需要考虑每一次要选择这一层的哪一个节点。显然我们不能从上向下每次选择子节点最多的树，那我们便要考虑从下至上更新每一层的状态，这也是树形dp的基本思路，即从最下边一层逐步选择子节点最多的节点更新到父亲节点，这样最后f[1]便是我们所求的答案。那么对于这一题，我们要对每一个节点更新第一需要考虑的便是每个节点下子节点的数量。因此我们首先要dfs一次将其求出。
代码如下：
void dfs1(int now,int father){ cnt[now]=1;//初始为1即自己，方便更新每一个节点的cnt for(int i=0;i<v[now].size();i++){ int op=v[now][i]; if(op==father) continue;//如果是父亲节点则跳过 dfs1(op,now);//递归求子节点的子节点数量 cnt[now]+=cnt[op];//更新答案 } }
now是当前节点，father是其父节点，cnt保存的是now的子节点的数量。v[now]保存的是与now相连接的节点。
至于为什么要将cnt[now]初始化为1，即倒数第二层可以更新加上最后一层的子节点，否则全都是0也加不了对吧，这样就可以一层一层累加起来了。
但是要注意的是，因为这里初始化了1，所以实际的子节点数量要减去1，即把自身减去了。
预处理子节点的数量后，我们便要考虑当一个节点已经被感染我们能拯救的最大子节点数量，我们设fi为i感染后可以拯救的最大子节点数。
注：红色为已经被感染的节点，蓝色是其父节点，黄色是其子节点
第一种，只有一条边：