Div 1 : “https://www.codechef.com/COOK123A/problems/PATHSUMS”

Div 2 : “https://www.codechef.com/COOK123B/problems/PATHSUMS”

My solution : “https://www.codechef.com/viewsolution/39006863”

Approach:-

Just assign value = 2 , for all even level nodes and value = 1 to all odd level nodes

Proof :

Let consider the path between two nodes whose length is even (>=2)

so what will be the pattern for value -

2 1 2 1 2 1

** OR **

1 2 1 2 1 2

means if path length is ** X ** then “2” occurs X/2 times and “1” also occurs X/2 times

total sum of this path values = (X/2)*2 + (X/2)*1 = (X + X/2) which is not completely divisible by X [path length] (as (n/2)%n !=0 it will be n/2 take n =6 then n/2 = 3 => 3%6 !=0 )

Now let consider the path between two nodes whose length is odd (>=3)

so what will be the pattern for value -

2 1 2 1 2

** OR **

1 2 1 2 1

means if path length is ** X ** then “2” occurs (X+1)/2 times and “1” occurs X/2 times

or “2” occurs X/2 times and “1” occurs (X+1)/2 times and in both case it will not completely divisible by X [ path length ] .

```
int vis[MAX];
vi adj[MAX];
lli depth[MAX];
void clear(lli n)
{
loop(i,n+1)
{
vis[i]=0;
adj[i].clear();
depth[i]=0;
}
}
void bfs(lli src)
{
vis[src]=1;
queue<lli>q;
q.push(src);
depth[src]=0;
while(!q.empty())
{
lli u = q.front();q.pop();
for(auto xt : adj[u])
{
if(!vis[xt])
{
vis[xt]=1;
q.push(xt);
depth[xt] = depth[u]+1;
}
}
}
}
int main(){
fastio
lli t=1;
cin>>t;
while(t--) {
lli n;
cin>>n;
loop(i,n-1)
{
lli x,y;
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
bfs(1);
lli a[n+1]={0};
FOR(i,1,n+1)
{
if(depth[i]%2)
{
a[i]=1;
}
else
a[i]=2;
}
FOR(i,1,n+1)
cout<<a[i]<<" ";
cout<<endl;
clear(n);
}
return 0;
}
```