/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 1.316 MiB
#2 Accepted 4ms 1.316 MiB
#3 Accepted 5ms 1.27 MiB
#4 Accepted 6ms 1.27 MiB
#5 Accepted 32ms 2.953 MiB
#6 Accepted 48ms 3.066 MiB
#7 Accepted 34ms 3.066 MiB
#8 Accepted 21ms 1.34 MiB
#9 Accepted 45ms 1.574 MiB
#10 Accepted 58ms 3.062 MiB
#11 Accepted 40ms 3.137 MiB
#12 Accepted 46ms 2.816 MiB
#13 Accepted 23ms 3.199 MiB
#14 Accepted 65ms 3.191 MiB
#15 Accepted 28ms 1.605 MiB
#16 Accepted 20ms 2.832 MiB
#17 Accepted 21ms 2.891 MiB
#18 Accepted 22ms 2.914 MiB
#19 Accepted 67ms 13.434 MiB
#20 Accepted 70ms 13.559 MiB
#21 Accepted 65ms 13.336 MiB
#22 Accepted 92ms 28.047 MiB
#23 Accepted 139ms 12.996 MiB
#24 Accepted 145ms 12.992 MiB
#25 Accepted 80ms 12.566 MiB
#26 Accepted 9ms 2.062 MiB

Code

#include<bits/stdc++.h>
using namespace std;
// #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<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define all(v) (v).begin(), (v).end()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define F first 
#define S second

const ll M = 1e18 + 7;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;

int root;
vector<int> adj[N];
int depth[N];
vector<int> check(N);

// int dfs(int node, int cost, int par) {

//     int tmp = 0;
//     for(auto it: adj[node]) {
//         if(it == par) continue;

//         depth[it] = depth[node] + 1;
//         tmp += dfs(it,2,node);
//     }

//     if(tmp == 0 && !check[node]) return 0;

//     return tmp + cost;
// }

void dfs2(int node, int par) {

    for(auto it: adj[node]) {
        if(it == par) continue;
        
        depth[it] = depth[node]+1;
        dfs2(it,node);
        check[node] = max(check[node],check[it]);
    }

}

void dfs3(int node, int par) {

    for(auto it: adj[node]) {
        if(it == par) continue;

        depth[it] = depth[node]+1;
        dfs3(it,node);
    }

}


void Hrid_solve(){
    int n;
    cin >> n;

    bool f = true;
    for(int i = 1; i <= n; i++) {
        cin >> check[i];
        if(check[i]) f = false;
    } 

    for(int i = 0; i < n-1; i++) {
        int u,v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if(f) {
        cout << 0 << endl;
        return;
    }

    int total = 0;
    int root = 0;
    int mx = -1;

    for(int i = 1; i <= n; i++) {
        if(check[i]) {
            // total = dfs(i,0,-1);
            dfs2(i,-1);
            root = i;
            break;
        }
    }
    for(int i = 1; i <= n; i++) {
        // cout << i <<  " " << check[i] << endl;

        if(check[i]) {
            if(depth[i] > mx) {
                mx = depth[i];
                root = i;
            }

            total++;
        }
        depth[i] = 0;
    }

    total = (total - 1) * 2;
    dfs3(root,-1);
    mx = -1;

    for(int i = 1; i <= n; i++) {
        if(check[i]) {
            if(depth[i] > mx) {
                mx = depth[i];
            }
        }
        depth[i] = 0;
        adj[i].clear();
        check[i] = 0;
    }
    // cout << mx << endl;    

    cout << total-mx << endl;
}


/* ************** What defines us is how well we rise after we Fall !! ************** */

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
 
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++){
        // cout << "Case " << kase << ": ";
        Hrid_solve();
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-17 18:38:05
Judged At
2024-10-03 13:16:54
Judged By
Score
100
Total Time
145ms
Peak Memory
28.047 MiB