/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 764.0 KiB
#2 Wrong Answer 1ms 344.0 KiB
#3 Wrong Answer 2ms 440.0 KiB

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 last_ver = 0;

// void Height(int node, vector<int> &vis, vector<int> &height, vector<int> adj[]) {
//     vis[node] = 1;

//     for(auto it: adj[node]) {
//         if(!vis[it]) {
//             Height(it,vis,height,adj);

//             height[node] = max(height[node], height[it]+1);
//         }
//     }
// }


int dfs(int node, int cost, vector<int> &vis, vector<int> check, vector<int> &depth, vector<int> adj[]) {
    vis[node] = 1;
    if(check[node]) last_ver = node;

    int tmp = 0;
    for(auto it: adj[node]) {
        if(!vis[it]) {

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

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

    return tmp + cost;
}

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

    int root = 0;
    vector<int> check(n), vis(n,0), depth(n,0);
    for(int i = 0; i < n; i++) {
        cin >> check[i];
        if(check[i]) root = i;
    } 

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

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

    // Height(0,vis,height,adj);
    int tmp = adj[0].size();
    int mx = 0;

    for(int i = 0; i < n; i++) {
        // cout << i+1 << " : " << height[i] << endl;
        vis[i] = 0;

        if(check[i]) {
            // if(height[i] <= tmp) root = i;
            if(adj[i].size() <= tmp) root = i;
        }
    }


    int ans = dfs(root,0,vis,check,depth,adj);
    for(int i = 0; i < n; i++) {
        if(check[i]) {
            mx = max(mx, depth[i]);
        }
    }

    // cout << mx << endl;
    cout << ans-mx << endl;
    
    last_ver = 0;
    
}


/* ************** 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 12:30:14
Judged At
2024-11-11 03:08:22
Judged By
Score
1
Total Time
2ms
Peak Memory
764.0 KiB