A. Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

I heard Alex really likes trees!

Given a tree, output "YES" if it produces oxygen, "NO" otherwise.

Input

A tree.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1-10$$$ are trees we found by going outside and touching grass. They produce oxygen.

Test $$$11-15$$$ are graph-theoretic trees. They do not produce oxygen. The first line contains $$$N$$$, the number of nodes. Nodes are indexed from $$$1$$$ to $$$N$$$. The next $$$N-1$$$ lines contain two integers $$$u$$$, $$$v$$$, representing an edge from node $$$u$$$ to node $$$v$$$.

Test $$$16-20$$$ are segment trees, written in C++ by various members of our problemsetting team. They do not produce oxygen.

Output

"YES" if the tree produces oxygen, "NO" otherwise.

Examples
Input
            ==                         
           ++==   =-                   
           ++=*+===:=    +=-           
           +*##***=-=*##*=====         
          +**%%#*#+*#%%%%%====         
    +++==++*+#%#**#%%#%%##*==-         
   ***##++##+*%%+%%%#%%#+*++=          
  *####%%#**##%%%%%%#**==*=++=         
  +*#%%%%%%%%%%%%%%%#*##***===+##+=    
 +#+*+#%%%%%#**#%%%##+*#++==###*#*=-   
  +++*+=-==*-=+**%#+*+**+=###++*+=-:-  
     +#=*####*+**#*++**#=+%%#*:++====  
     *#######*+**=*%##%#*+-*#-:==      
    ###*#*%##%*+*+%%%%##**++-+***#++-- 
  *####+=#@%####%%%%%%**+===+#####%#-:-
 +#*###*###%%***%%%@++*=#+-+#****+++*=-
+++*#%%%%%%#%%#%%@%%+--###+#**%#+-====-
 ++##%%%%%%#%%#*%%%%+#*%%*#%=+**=-     
  *+###%%%++%%%##%*####%%#*##+-+=-     
    %%%%%##*####+##%%%%%##*#*++++-=    
   #*#%%%#%*+#%%%%%#%%%%#+##%*#*+=-    
    **####%*=##%%%%##%%**+*#*#=#+=     
     *****#*++#%%%%+-%*+=*+=*+==+=     
      ++++*+  #%##*#=#+=- =+=+ -=      
              *###*#+=+--   =          
               *###=+==:-              
                *##*=::-               
                  +#-::                
                   #-.                 
                   #-.                 
                   *:.                 
                   #=.                 
                   *-.                 
                   *-.                 
                   *=.                 
                   *=.                 
                   *-.                 
                   *=.                 
                   *-.                 
                   *-.                 
                   *-.                 
                   #*==                
                 ###*#+*=              
                #%#%-=+:=+             
               %##%%:--.--             
               ++*%#--+-+=             
               ##*%#=-=:-+             
               #*##=*=----             
              *##%*=%+*#=+=**          
             %##+*=+*###+-#=++         
            %%#=%+=*+*%**=--=          
            ##++#++**%%*+=-==          
            %%*+###+*#%*%=+-           
             %%*###++%*+##--           
             %%%%#++=%%+=*=-           
             %%%##+=+%%*+=++           
             %%%%%+#+#%%+*#+           
            %%%%%*#+**#%#*#*%          
            %%%%**+*=+#+*#-+*          
            %%%%*%#*==#*=**+=          
             %%%#%#==+#*=+=*%          
             #%%%%##+**+=+=*#          
            *#%%%%#*-*%%===*#          
             %%%%##%-+%%++=%           
             %%##=%#==*#++=#           
             %%#%%%*++-=+*++           
             %@%%#%%#+=:**=%           
             %%%##%%**==**+%           
             %%#+#+%++-==++%           
             ####*+%**+==+=+           
             #%%%%*==++*+++#           
             %%%##%%===+*=*%           
             %%%#*%#==*++=+%           
             *%%*%%#-=+=**+%           
             +###%%%*=+#+=*%           
             .-%#%#%%%*:=+*            
             .:#+#+**#-*+-.            
               -.##+=-.:=+%            
                .#*+=:..               
                :*+=*-.                
                %%#=*:.                
                %%#==:.                
                %%**--.                
                %#+=-:.                
                %%+=--.                
               %%#+-=-=                
               +%%+=:--                
               %+*#+*-+                
               %#**+*=+                
                #**##==
Output
YES
Input
5
1 3
1 4
3 5
2 3
Output
NO
Input
#include <bits/stdc++.h>
using namespace std;

int arr [1000000];
int va [1000000];
int lc [1000000];
int rc [1000000];

int curnod = 5;

int newnod(){
    return ++curnod;
}

void construct(int cur, int l, int r){
    if(l == r){
        va[cur] = arr[l];
    }else{
        lc[cur] = newnod();
        rc[cur] = newnod();
        construct(lc[cur], l, (l+r)/2);
        construct(rc[cur], (l+r)/2+1, r);
        va[cur] = min(va[lc[cur]], va[rc[cur]]);
    }
}

void change(int cur, int l, int r, int k, int u){
    if(l <= k && k <= r){
        if(l == r){
            va[cur] = u;
        }else{
            change(lc[cur], l, (l+r)/2, k, u);
            change(rc[cur], (l+r)/2+1, r, k, u);
            va[cur] = min(va[lc[cur]], va[rc[cur]]);
        }
    }
}

int query(int cur, int l, int r, int fl, int fr){
    if(fl <= l && r <= fr){
        return va[cur];
    }else if(r < fl || fr < l){
        return 1000000000;
    }else{
        return min(query(lc[cur], l, (l+r)/2, fl, fr), query(rc[cur], (l+r)/2+1, r, fl, fr));
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    int root = newnod();
    construct(root, 1, n);
    for(int i = 0; i < q; i++){
        int o;
        cin >> o;
        if(o == 1){
            int k, u;
            cin >> k >> u;
            change(root, 1, n, k, u);
        }else{
            int l, r;
            cin >> l >> r;
            cout << query(root, 1, n, l, r) << endl;
        }
    }
}
Output
NO
Note

The first sample test case is a California Fan Palm. Although botanically speaking, palm trees are not true trees, this tree certainly undergoes photosynthesis and produces oxygen.

The second sample test case is a connected undirected acyclic graph; i.e., a graph-theoretic tree. It contains 5 nodes, numbered 1, 2, 3, 4, and 5. It has an edge connecting node 1 and node 3, node 1 and node 4, node 3 and node 5, and node 2 and node 3. This tree has only three leaves: nodes 2, 4, and 5, and the leaves do not have any chlorophyll. Thus, this tree does not produce oxygen.

The third sample test case is a segment tree, written in C++ by alexlikemath007. Although segment trees can combine segments together to perform range queries, they cannot combine water, carbon dioxide, and sunlight together to perform photosynthesis. Thus, this tree does not produce oxygen.