admin管理员组文章数量:1530017
BerSoft is the biggest IT corporation in Berland. There are n n n employees at BerSoft company, numbered from 1 1 1 to n n n.
The first employee is the head of the company, and he does not have any superiors. Every other employee i i i has exactly one direct superior p i p_i pi.
Employee x x x is considered to be a superior (direct or indirect) of employee y y y if one of the following conditions holds:
- employee x x x is the direct superior of employee y y y;
- employee x x x is a superior of the direct superior of employee y y y.
The structure of BerSoft is organized in such a way that the head of the company is superior of every employee.
A programming competition is going to be held soon. Two-person teams should be created for this purpose. However, if one employee in a team is the superior of another, they are uncomfortable together. So, teams of two people should be created so that no one is the superior of the other. Note that no employee can participate in more than one team.
Your task is to calculate the maximum possible number of teams according to the aforementioned rules.
Input
The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n n n ( 2 ≤ n ≤ 2 ⋅ 1 0 5 2 \le n \le 2 \cdot 10^5 2≤n≤2⋅105) — the number of employees.
The second line contains n − 1 n-1 n−1 integers p 2 , p 3 , … , p n p_2, p_3, \dots, p_n p2,p3,…,pn ( 1 ≤ p i ≤ n 1 \le p_i \le n 1≤pi≤n), where p i p_i pi is the index of the direct superior of the i i i-th employee.
The sum of
n
n
n over all test cases doesn’t exceed
2
⋅
1
0
5
2 \cdot 10^5
2⋅105.
Output
For each test case, print a single integer — the maximum possible number of teams according to the aforementioned rules.
贪心+树形dp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 4e5 + 10;
int h[N], e[M], ne[M], idx;
int sz[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void init(int u)
{
sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
init(v);
sz[u] += sz[v];
}
}
int dfs(int u, int k)
{
int tot = 0, mx = -1;
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
tot += sz[v];
if (mx == -1 || sz[mx] < sz[v])mx = v;
}
if (tot == 0)return 0;
if (sz[mx] - k <= tot - sz[mx])
return (tot - k) / 2;
int add = tot - sz[mx];
return add + dfs(mx, max(0, add + k - 1));
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
memset(h, -1, sizeof h);
idx = 0;
for (int i = 2; i <= n; i++)
{
int p;
cin >> p;
add(p, i);
}
init(1);
cout << dfs(1, 0) << endl;
}
}
本文标签: Programmingcompetition
版权声明:本文标题:F. Programming Competition 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1726693592a1080941.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论