Can you share the editorial of Cherry and Squares
It is not fully prepared. Will post it by tomorrow. 
Consider this case
1
8 1
1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 7
2 5
5 6
6 8
5
If two nodes are at different even depths it doesn’t necessarily mean that one is in the subtree of the other.
Your output - 1 1 1 1 3 1 0 0
Correct output - 1 1 1 1 2 1 1 0
3 Likes
Okay thanks.
Don’t know why getting Tle … i think its a O(n) solution. ti would be great help if someone help me finding the reason .
https://www.codechef.com/viewsolution/37002710
Oh dang, that was stupid of me.
Thank you for taking the time to go through it!
I’ll upsolve this tomorrow.
Hello, can you tell me on which test-case does my solution fails ?
https://www.codechef.com/viewsolution/37006323
Same idea as that of the editorial.
@aert
@aert @cub Can anyone please help me find where my solution fails :CodeChef: Practical coding for everyone
@aryanc403
1 Like
I haven’t properly seen your code but it fails on
1
8 3
1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 7
2 5
5 6
6 8
7
3
1
Your output - 4 1 0 1 0 1 0 1
Correct output - 5 1 0 1 0 1 0 0
I was coding segment tree along with euler tour. Only Update function was left when I realised one doesn’t need it. 
“Things to watch out for” Did got one TLE due to this.
2 Likes
What is wrong with this → CodeChef: Practical coding for everyone
Please help someone .I used BFS and created a distance array for each Node.
I am getting runtime array but it is working fine for the sample test case.
Thanks brother , I was missing a Q.pop() operation when I was using continue statement But after correcting it also I am getting correct answer on your test case but WA during submission. Can you now tell me some test cases where my solution is failing . Thanks in advance.
https://www.codechef.com/viewsolution/37007493
Actually your approach is not correct. We have to transfer the values of nodes at even distance to the source node “present in that subtree”.
But according to your approach you are transfering values of all nodes whose depth is even from that node, so there may be some nodes which can not be present in that subtree.
1 Like
" You are given a tree rooted at node 1 with N vertices."
This is the first line of the question .
3 Likes
Can somebody help me out finding what is wrong with this solution. Thanks in advance!
https://www.codechef.com/viewsolution/37003547
Can anybody explain me this…It is written in the editorial that “if visited[vertex][1] == 1, all the nodes at odd distance from the current vertex are zero. So there is no need to go further.” but, aren’t we interested in the nodes at even distance from the vertex so why no need to go further?
My Sol with just one simple DFS to do the work :)
`//
// author : Abhishek
//
#include <bits/stdc++.h>
#include
#define ll long long
#define db double
#define deb(x) cout<<#x<<“: “<<x<<”\n”
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)
#define setBits(x) __builtin_popcountll(x)
#define parity(x) __builtin_parity(x)
using namespace std;
using namespace chrono;
const ll MOD = 1000000007;
const ll N = 300005; // array size
const ll inf = 10000000000000000;
const db PI = 3.14159265358979323846264338327950288419716939937510;
void print(vector v) {
ll i;
fo(i, v.size())cout << v[i] << " ";
cout << “\n”;
}
void print(vector<pair<ll, ll> > v) {
ll i;
fo(i, v.size()) {
cout << v[i].first << " " << v[i].second << “\n”;
}
}
vector read(ll n) {
ll i;
vector arr(n, 0);
fo(i, n)cin >> arr[i];
return arr;
}
vector read(ll n, ll k) {
ll i;
vector arr(n + k, 0);
Fo(i, k, n + k)cin >> arr[i];
return arr;
}
bool isEven(ll n) {
return n % 2 == 0;
}
bool isOdd(ll n) {
return n % 2 != 0;
}
vector adj[N];
vector vis(N, 0);
vector taken(N, 0);
vector ans(N, 0);
vector depth(N, 0);
pair<ll, ll> dfs(ll cur, bool takenEv, bool takenOd) {
vis[cur] = true;
pair<ll, ll> forThis = {0, 0};
if (isEven(depth[cur])) {
forThis.first += ans[cur];
} else {
forThis.second += ans[cur];
}
for (auto next: adj[cur]) {
if (!vis[next]) {
depth[next] = 1 + depth[cur];
pair<ll, ll> ct;
if (taken[cur]) {
if (isEven(depth[cur])) {
ct = dfs(next, true, takenOd);
} else {
ct = dfs(next, takenEv, true);
}
} else {
ct = dfs(next, takenEv, takenOd);
}
forThis.first += ct.first;
forThis.second += ct.second;
}
}
if (takenEv && isEven(depth[cur])) {
ans[cur] = 0;
} else if (takenOd && isOdd(depth[cur])) {
ans[cur] = 0;
} else if (taken[cur]) {
ans[cur] = (isEven(depth[cur]) ? forThis.first : forThis.second);
}
return forThis;
}
void solve() {
ll t = 1, cs = 1;
cin >> (t);
while (t–) {
ll i, j, k, n, m, p, q, x, y, a, b, l, r;
cin >> n >> q;
Fo(i, 1, n + 1) {
adj[i].clear();
taken[i] = 0;
ans[i] = 0;
vis[i] = false;
}
Fo(i, 1, n + 1) {
cin >> ans[i];
}
fo(i, n - 1) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
while (q--) {
cin >> x;
taken[x] = 1;
}
dfs(1, 0, 0);
// Fo(i, 1, n + 1) {
// cout << depth[i] << " ";
// }
// cout << “\n”;
Fo(i, 1, n + 1) {
cout << ans[i] << " ";
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
freopen(“error.txt”, “w”, stderr);
#endif
auto start = high_resolution_clock::now();
solve();
ll i, j, k, n, m, p, q, x, y, a, b, l, r;
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
#ifndef ONLINE_JUDGE
cerr << "Time: " << duration.count() / 1000.0 << endl;
#endif
return 0;
}
`
bro! anyone there who can help me . i have written code using euler tour but still showing tle. and i have checked it for many test cases and even given in the comments too.
here is my ideone link