#include
#define llu long long unsigned
#define MAXSIZE 10000
#define pb push_back
using namespace::std;
typedef vector vi;
typedef pair < int, int > ii;
typedef vector < ii > vii;
typedef vector vvii;
typedef vector < vi > vvi;
//r2 keeps track of the no. of children of root of /**each**/ tree in the forest which are labeled 1
map r2;
map aux_map;
vi tree;
llu dfs(vvi &g, vector &vs, int v, map &r2, vi &key)
{
vs[v] = true;
llu c = 1; //contribution of the node on which dfs has been called, ...we'll return c-1 later if this nodes window is closed
for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
if(!vs[*it])
c += dfs(g, vs, *it, r2, key); //increment c by the no of open window nodes rooted at c
if(key[v]) {
r2[v] = c ; //map r2 keeps track of no. of open window nodes rooted at each node of the graph
return c ;
}
{
r2[v] = c-1 ; //if the node has its window closed,adjust its contribution which was initiated as 1
return c-1;
}
}
void drought(vvi &g, vi &key, int V, vi &r1)
{
vector vs(V+1, false);
vs[0] = true;
for(int i = 1 ; i <= V ; ++i)
if(!vs[i])
{
tree.pb(i); // the vector tree keeps track of root of each tree in the forest
r1.pb(dfs(g, vs, i, r2, key)); //the vector r1 stores the no of 'open window' nodes rooted at each root of the forest including the status of root
}
}
long long unsigned calculate(vi tree, map &r2)
{
long long unsigned count = 0;
for(auto it = tree.begin() ; it != tree.end() ; ++it)
count += (r2[*it]*(r2[*it]-1))/2;
return count;
}
int main()
{
int V, E, s, d, w, st;
//cout<<"\nenter the no of nodes and edges :\t ";
cin>>V>>E;
for(int i = 0 ; i <= V ; ++i)
{
r2[i] = 0;
aux_map[i] = 0;
}
vi r1;
vi key(V+1);
vvi g(V+1);
//cout<<"\nenter the window status \n";
key[0] = 0;
for(int i = 1 ; i <= V ; ++i)
{
cin>>st;
key[i] = st;
}
//cout<<"\nenter each edge\n";
for(int i = 0 ; i < E ; ++i)
{
cin>>s>>d;
g[s].pb(d);
g[d].pb(s);
}
drought(g, key, V, r1);
/*cout<<"\nno of open window children rooted @ a prticular node(including its own status) : node -> open window children "< "< 0 && r2[x] < root_id) //element has at least 1 open window child also there is some open window node rooted at the same root at which the element is hence at least the way between these 2 nodes connects 'em
count++;
else if(key[x] == 1 && r2[x] > 1) //element has its window open and has at least one open window child, hence the path bw them connects 'em
count++;
else //else for the element must have at least two open window nodes rooted @ itself
{
vector vsz(x - *it1, true); //mark all the nodes b4 x visited as we are interested to find the no. of open window nodes of subtree rooted @ x
for(llu i = x ; i < *it2 ; ++i) //mark all the remaining nodes(including itself) in the tree unvisited
vsz[i] = false;
if(key[x]) //if the node has its window open calling dfs on it returns 1+no. of open window nodes rooted @ it
{
if(dfs(g, vsz, x, aux_map, key) >= 3)
count++;
}
else if(dfs(g, vsz, x, aux_map, key) >= 2) //else if the node has its window closed calling dfs on it returns no. of open window nodes rooted @ it
count++;
}
x++;
}
it1++; /*increment the tree*/
it2++;
}while(*it1 != V+1);
//cout<<"\nthe result of query 2 is :\t";
cout<