Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iomanip>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <utility>
- #include <vector>
- using namespace std;
- #define sc(a) scanf("%d", &a)
- #define sc2(a, b) scanf("%d%d", &a, &b)
- #define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
- #define pri(x) printf("%d\n", x)
- #define prie(x) printf("%d ", x)
- #define mp make_pair
- #define pb push_back
- #define BUFF ios::sync_with_stdio(false);
- #define db(x) cerr << #x << " == " << x << endl
- #define dbs(x) cerr << x << endl
- #define imprime(x, Y) \
- for (int X = 0; X < Y; X++) cerr << x[X] << " "; \
- cerr << endl;
- typedef long long int ll;
- typedef long double ld;
- typedef pair<int, int> ii;
- typedef vector<int> vi;
- typedef vector<ii> vii;
- typedef vector<vi> vvi;
- typedef vector<vector<ii> > vvii;
- const int INF = 0x3f3f3f3f;
- const ll LINF = 0x3f3f3f3f3f3f3f3fll;
- const ld pi = acos(-1);
- const int MOD = 1e9 + 7;
- const int N = 100010;
- int t, c, k, n;
- vi graph[N];
- int us[N], level[N], level2[N];
- void dfs(int u, int l)
- {
- us[u] = 1, level[u] = l;
- for (int v : graph[u])
- if (!us[u]) dfs(v, l + 1);
- }
- void dfs2(int u, int l)
- {
- us[u] = 1, level2[u] = l;
- for (int v : graph[u])
- if (!us[u]) dfs2(v, l + 1);
- }
- ii extremos()
- {
- int b = -1, e = -1;
- memset(us, 0, sizeof(us));
- dfs(1, 1);
- int idx = 0, romario = 0;
- for (int i = 1; i <= n; i++)
- if (level[i] < romario) romario = level[i], idx = i;
- memset(us, 0, sizeof(us));
- b = idx;
- dfs(b, 1);
- idx = 0, romario = 0;
- memset(level, 0, sizeof(level));
- for (int i = 1; i <= n; i++)
- if (level[i] < romario) romario = level[i], idx = i;
- e = idx;
- return mp(b, e);
- }
- int main()
- {
- sc(t);
- for (int Y = 0; Y < t; Y++) {
- for (int i = 0; i < N; i++) graph[i].clear();
- sc2(c, k);
- for (int j = 0; j < c; j++) {
- sc(n);
- for (int i = 2; i <= n; i++) {
- int x;
- sc(x);
- graph[x].pb(i);
- graph[i].pb(x);
- }
- ii ext = extremos();
- memset(us, 0, sizeof(us));
- dfs(ext.first, 0);
- memset(us, 0, sizeof(us));
- dfs2(ext.second, 0);
- for (int i = 1; i <= n; i++) level[i] = max(level[i], level2[i]);
- int menorigual = 0;
- for (int i = 1; i <= n; i++) menorigual += (level[i] <= k);
- double prob = menorigual / (double)n;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement