题目思路：
先说一下题目的意思吧，我一开始还真是看不懂，路径到底指的是什么。
后来才慢慢懂了，原来他的路径指的是有几条线（可以是折线，但这一条折线不能通过重复的地方）可以把所有的边走遍。
对于可以覆盖的情况，这边只需要统计出有多少个叶子，由于一棵树，你从一个点出发，你可以到达任意的一个点。
所以这个答案就是(叶子数cnt+1)/2
对于不可以覆盖的情况看代码注释了。
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;#define MAX 100005vector<int> g[MAX];int du[MAX];int ans = 0;void dfs(int u, int p, int flag){//搜这个子树，看看他有多少个子链。//假设有k个子链，，一个路径可以覆盖两条子链，经过父点//这样的话，假如k为偶数，那么路径数为k/2，假如为奇数的话，k/2，少了一条，所以需要加上1，即（k+1）/2；//由于是子树，所以有父节点，会有一条与子树连接的路径，该条路径又可以与该子树的一条链相连，这样的话，最后的结果应该是(k-1+1)/2int sum = 0;//记录子链的个数for (int i = 0; i < g[u].size(); i++){int v = g[u][i];if (v == p)continue;sum++;dfs(v, u, 1);//1表示他是一个子树}ans += (sum – flag + 1) / 2;}int main(){int t;cin >> t;while (t–){ans = 0;int n;scanf("%d", &n);for (int i = 0; i < n; i++){du[i] = 0;g[i].clear();}int u;for (int i = 1; i < n; i++){scanf("%d", &u);du[u]++;du[i]++;g[i].push_back(u);g[u].push_back(i);}int cnt = 0;for (int i = 0; i < n;i++)if (du[i] == 1)cnt++;if (n == 1)cnt = 0;elsecnt = (cnt + 1) / 2;dfs(0, 0, 0);printf("%d %d\n", cnt, ans);}}
当你见过了世界上最美丽的风景，
