Submission #70151017

---

Source Code Expand

// To scale the heights, one must embrace the fall.
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define pb emplace_back
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int n, ans, p[N], sz[N];
vector<int> G[N];
void dfs(int u) {
    sz[u] = 1;
    for (int v : G[u]) {
        dfs(v), sz[u] += sz[v];
    }
}
void dfs(int u, int lim) {
    int mx = 0, sum = 0;
    for (int v : G[u]) {
        sum += sz[v];
        if (sz[v] > sz[mx]) mx = v;
    }
    if (sz[mx] * 2 <= sum) {
        ans += min(lim, sum / 2);
        return;
    } else {
        ans += sum - sz[mx];
        dfs(mx, min(lim - sum + sz[mx], sz[mx] * 2 - sum >> 1));
    }
}
void solve(int TC) {
    cin >> n;
    F(i, 1, n) G[i].clear();
    ans = 0;
    F(i, 2, n) {
        cin >> p[i];
        G[p[i]].pb(i);
    }
    dfs(1);
    dfs(1, n / 2);
    cout << ans << '\n';
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i ++) {
        solve(i);
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void dfs(long long int, long long int)’:
Main.cpp:34:52: warning: suggest parentheses around ‘-’ inside ‘>>’ [-Wparentheses]
   34 |         dfs(mx, min(lim - sum + sz[mx], sz[mx] * 2 - sum >> 1));
      |                                         ~~~~~~~~~~~^~~~~
Main.cpp: In function ‘void solve(long long int)’:
Main.cpp:37:16: warning: unused parameter ‘TC’ [-Wunused-parameter]
   37 | void solve(int TC) {
      |                ^

Judge Result