/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 9ms 9.605 MiB
#2 Accepted 9ms 9.52 MiB
#3 Accepted 9ms 9.641 MiB
#4 Accepted 11ms 9.676 MiB
#5 Accepted 33ms 11.168 MiB
#6 Accepted 52ms 11.281 MiB
#7 Accepted 44ms 11.367 MiB
#8 Accepted 27ms 9.555 MiB
#9 Accepted 52ms 9.945 MiB
#10 Accepted 70ms 11.328 MiB
#11 Accepted 47ms 11.469 MiB
#12 Accepted 53ms 11.391 MiB
#13 Accepted 28ms 11.289 MiB
#14 Accepted 68ms 11.484 MiB
#15 Accepted 37ms 10.094 MiB
#16 Accepted 25ms 11.391 MiB
#17 Accepted 25ms 11.301 MiB
#18 Accepted 23ms 11.266 MiB
#19 Accepted 73ms 21.926 MiB
#20 Accepted 73ms 21.48 MiB
#21 Accepted 74ms 21.84 MiB
#22 Accepted 111ms 44.871 MiB
#23 Accepted 165ms 20.645 MiB
#24 Accepted 164ms 20.641 MiB
#25 Accepted 90ms 20.34 MiB
#26 Accepted 14ms 10.871 MiB

Code

///**Bismillahir Rahmanir Raheem**
///**       Mizanul Hoque       **
///**           IIUC            **
/// ###############################
#include <bits/stdc++.h>
using namespace std;
/// POLICY BASED DATA STRUCTURE..
/// order_of_key return number of element which are strictly greater/smaller than x..
/// find_by_order return ans iterator corresponding to the xth position of the set..

// #include<ext/pb_ds/assoc_container.hpp>
//  #include<ext/pb_ds/tree_policy.hpp>
//  using namespace __gnu_pbds;
//  #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

#define faster                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define sz(n) (int)(n).size()
#define eps 1e-10

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;

#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define max3(a, b, c) max(c, max(a, b))
#define max4(a, b, c, d) max(d, max(c, max(a, b)))

#define pi 2 * acos(0) /// acos(-1.0)
#define deg_to_rad(x) ((x) * ((2 * acos(0)) / 180.0))
#define rad_to_deg(x) ((x) * (180.0 / (2 * acos(0))))

#define fi first
#define sc second
#define mp make_pair
#define __lcm(a, b) (a / __gcd(a, b) * b)

typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int M = 1e9 + 7;
const int N = 200020;

// ll n,m,i,k,h;

vector<ll> prime_divisor[N];
int vis[N];
vector<int> edge[N];

bool cmp(pair<ll, ll> p1, pair<ll, ll> p2)
{
    return p1.fi < p2.fi;
}
int height[N];
int dep[N];
int last[N];
ll a[N];
int siz[N];
ll ans = 0;
void dfs(int u, int par)
{
    last[u] = (a[u] == 1);
    siz[u] = 1;
    for (auto v : edge[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
        last[u] += last[v];
        // last[u] += (a[v] == 1);
        siz[u] += siz[v];
    }
}
void dfs1(int u, int par)
{
    height[u] = 0;
    vector<int> vec;
    if (last[u] == 0)
    {
        ans -= (siz[u] * 2);
    }
    else
    {
        for (auto v : edge[u])
        {
            if (v == par)
                continue;
            if (last[v] == 0)
            {
                ans -= (siz[v] * 2);
                continue;
            }
            dfs1(v, u);
            vec.pb(height[v]);
            height[u] = max(height[u], height[v] + 1);
        }
        sort(all(vec));
        if (sz(vec) == 0)
        {
            dep[u] = 0;
        }
        else if (sz(vec) == 1)
        {
            dep[u] = vec[sz(vec) - 1] + 1;
        }
        else
        {
            dep[u] = vec[sz(vec) - 1] + vec[sz(vec) - 2] + 2;
        }
    }
}

void solve()
{
    ll i, j, k, n, m, p, q, x, y, z, u, v, l, r, mod = 1e9 + 7, mx, mn, mx1, mn1, cnt1, cnt;
    cin >> n;
    int pos = -1;
    cnt=0;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] == 1)
        {
            cnt++;
            pos = i;
        }
    }
    for (i = 0; i < n - 1; i++)
    {
        cin >> u >> v;
        edge[u].pb(v);
        edge[v].pb(u);
    }

    if (pos == -1)
    {
        cout << 0 << endl;
    }
    else if(cnt==1)
    {
        cout<<0<<endl;
    }
    else
    {
        dfs(pos, -1);
        ans = 0;
        ans = (n - 1) * 2;
        // cout<<ans<<endl;
        dfs1(pos, -1);
        int mxx = 0;
        for (i = 1; i <= n; i++)
        {
            mxx = max(mxx, dep[i]);
        }
        ans -= mxx;
        cout << ans << endl;
    }
    for (i = 1; i <= n; i++)
    {
        edge[i].clear();
        dep[i]=0;
    }
}

int main()
{
    faster;
    ll tc = 1;
    cin >> tc;
    for (ll t = 1; t <= tc; t++)
    {
        /// cout<<"Case "<<t<<": ";
        solve();
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Contest
Bangladesh 2.0
Language
C++17 (G++ 13.2.0)
Submit At
2024-08-16 17:26:46
Judged At
2024-11-11 03:11:45
Judged By
Score
100
Total Time
165ms
Peak Memory
44.871 MiB