### PROBLEM LINK:

**Author & Editorialist:** Pulkit Sharma

**Tester:** Satyam Gupta

### DIFFICULTY:

EASY

### PREREQUISITES:

Graphs, (DFS)

### PROBLEM:

Given a Tree , find whether whether all the nodes of a tree satisfy the condition to make it an alternating tree. Read here to see details.

### EXPLANATION:

let state store the state at which the current node is. There are two possible states . crest or trough.

What the problem boils down is to find whether all the paths from root to the leaves is of the form [crest,trough,crest,...] or [trough,crest,trough...] .

This can easily be done using DFS.

To start with DFS , we first need to find the state of the root node.

This can be done by comparing it with its children.

If all the child nodes have a value greater than the root , then the root's state is trough , stored as 0.

Similarly, if all the child nodes have a value less than the root, then the root's state is crest , stored as 1.

If none of the above is true , then the root is in an invalid state.

So, straightaway the tree is **Not an Alternating Tree**.

Once we have the root's state, we can start with our DFS . But we need to slightly modify the standard DFS implementation as we have to keep track of the state of the current node the DFS has reached.

The following DFS skeleton code should help you to understand:

```
DFS(node,state)
//other necessary code
if state = 0
//every child should be greater than it
for all children
if(child_i is greater than node)
DFS(child_i,1-state) //IMPORTANT , change the state
else
//exit from DFS, not an alternating Tree
if state = 1
//every child should be smaller than it
for all children
if(child_i is smaller than node)
DFS(child_i,1-state) //IMPORTANT , change the state
else
//exit from DFS, not an alternating Tree
```

If the DFS did not prematurely end, then depending upon the state of the root we can print our answer.

If the DFS did end prematurely , then the tree is not an Alternating Tree

### AUTHORâ€™S SOLUTION:

```
#include<iostream>
#include<list>
#include<vector>
#include<cstdio>
using namespace std;
int a[10005];
vector< list<int> > g(10005);
bool notset,mat,nat;
void dfs(int x,bool y)
{
for(list<int>::iterator it=g[x].begin();!nat && it!=g[x].end();it++)
{
if(notset)
{
if(a[x]<a[*it]) mat=1;
else y=mat=0;
notset=0;
}
else
{
if((!y && a[x]<a[*it])||(y && a[x]>a[*it]))
{nat=1;return;}
}
//printf("\n[%d,%d] (%d,%d,%d)",x,*it,notset,mat,nat);
dfs(*it,!y);
}
}
int main()
{
cin.sync_with_stdio(false);
cin.tie(NULL);
int t,i,j,n,x,y;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++){cin>>a[i];g[i].clear();}
nat=0;
notset=1;
for(i=0;i<n;i++)
{
cin>>x;
for(j=0;j<x;j++)
{
cin>>y;
g[i].push_back(y);
}
}
dfs(0,1);
if(nat) cout<<"NAT\n";
else if(mat) cout<<"MAT\n";
else cout<<"VAT\n";
}
return 0;
}
```