simply assign 1 to the root and after that do a dfs search and assign 2 to a node if its parent has value 1 and assign 1 if its parent has value 2.
Clear your graph too, after each test case.
1 Like
Donāt know what is wrong with this codeā¦simple BFSā¦
#include<bits/stdc++.h>
#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 int
#define fast_io ios_base::sync_with_stdio(false)
#define endl "\n"
using namespace std;
vector<int>graph[100];
int dis[105] = {0};
int odd=1,even=2;
void bfs(int u, vector<bool>visited, vector<int>&ans)
{
visited[u]=true;
queue<int>q;
q.push(u);
while (q.size() != 0)
{
int current=q.front();
q.pop();
for(auto it:graph[current])
{
if(visited[it]==false)
{
visited[it]=true;
q.push(it);
if(ans[current]==1)
ans[it]=2;
else
ans[it]=1;
}
}
}
}
int main()
{
fast_io;
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
graph[n + 1];
for(int i=0;i<=n;i++)
graph[i].clear();
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<bool>visited(n , false);
vector<int>ans(n);
ans[0] = 1;
ans[1] = 2;
bfs(1, visited, ans);
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}The path not necessarily starts or ends at a leaf node. Take 1->2->3 as an example. You assign P to 1 and 2, and 2P to 3. 1->2 is also a valid path, whose length is 2 and sum is 2P which is divisible by 2.
Found the issue, I missed to clear my map after every test case.
Yea it worked thanks
A small mistake during costed a lot 
1 Like
Change your vector visited and ans size from n to (n+1) 
Such a nice question
I did same but got WA.
bro you thought everything right but missed one thing. dfs would give wrong answer in some cases. you check yourself in the example that you gave assign alternate 1, 2 from A TO I nodes and you will see that either 1 and 1 will be assigned to A and C which are adjacent or 2 and 2 will be assigned which will be divisible by 2.
BFS will work here.
By the way nice video 
Why is this code giving WA. I have done this question by BFS.
https://www.codechef.com/viewsolution/39072313
You are passing reference for visited vector ; pass the Visit vector as pointer in the bfs() functionā¦ as like
bfs(int s,vector&vis,vector&ans)
one more thing ; you may be just forgot but should be cautious on this ; you didnāt have any return type for bfs() and main() but you defined them as int() ā¦ So it could suffer you in some platforms. I am not sure if codechef has any issue with functionās return type though this is not an issue for getting WA in this problem.
Anyway , your main problem was with passing visited vector as referenceā¦ Happy Codingā¦
Thank you so much. My problem has been solved.
1 Like
https://www.codechef.com/viewsolution/39126236
Check Out my solution
Iāve also used vectors of vectors and assigned value 1 and 2 alternatively to the parent and child.
If parent is 1 then child is 2 and vice versa.
I tried another approach - set value for each non-leaf node to 2 and leaf nodes to 1.
Can anyone explain why this approach is wrong?
It is not necessary that a simple path in a tree starts or ends in a leaf node. Consider this tree - 1 -> 2 -> 3. Here you assign 2 to nodes 1 and 2, and you assign 3 the value 1. But 1->2 is also a valid path. So here the sum is 4 which is divisible by 2.
Thanks, I considered the path only between leaf nodes
I dont understand ,here
void dfs(int u,int p)
{
nums[u]=(nums[p]&1)?2:1;
for(auto v: graph[u])
{
if(v!=p)
{
dfs(v,u);
}
}
}
here ,after we reached the last node then how can we again trace back?