QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#755#478462#7936. Eliminate TreedeepthoughtembuscaFailed.2024-07-29 04:34:572024-07-29 04:34:57

Details

Extra Test:

Invalid Input

input:

9
1 2
3 2
3 4
3 5
5 6
5 7
5 8

output:


result:

FAIL Unexpected end of file - token expected (stdin, line 9)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478462#7936. Eliminate Treeembusca#AC ✓63ms15820kbC++201.2kb2024-07-14 23:21:242024-07-14 23:21:25

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rp(i,a,b)        for(int i=a;i<b;i++)

const int N = 2e5+10;
vector<int> adj[N], vals;
vector<bool> used;
int resp = 0;

void dfs(int v, int p = -1){
    //cout << v << " " << resp << "!\n";
    for(auto ch : adj[v]) if(ch != p){ 
        dfs(ch, v);
        if(vals[ch] == 0){
            vals[v]--;
        }
    }
    for(; vals[v] > 2 - (p==-1); vals[v]--){
        // cout << "DIMINUINDO V " << v << "\n";
        resp += 2;
    }

    if(p == -1){

        // cout << "ROOT \n";
        resp += (vals[v] == 0 ? 2: 1);
    }
    else if(vals[v] == 2){
        // cout << "CORTEI V " << v << '\n';
        resp++;
        vals[v] = 0;
    }
    //cout << v << " " << resp << "?\n";
}

void solvetask(){
    int n;
    cin >> n;
    used.assign(n+1, false);
    vals.assign(n+1, 0);
    rp(i, 1, n){
        int u, v;
        cin >> u >> v;
        // u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    rp(i, 1, n+1) vals[i] = adj[i].size();
    dfs(1);

    cout << resp << "\n";
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    while(t--) solvetask();
}