I have written the code to solve [this](http://mirror.codeforces.com/contest/764/problem/C) problem, but it gives TLE. I think the complexity of my soln. is O(n). ↵
My approach is as follows:↵
↵
`Let dp[from][to] = 1 if all nodes in the subtree of "to" (including "to") are of the same color when we perform dfs from node "from" and "to" is the child of node "from".`↵
`dp[from][to] = 0, otherwise.`↵
↵
↵
↵
↵
`To calculate dp[from][to] we use dfs. Let node "to" have k children, then let's compute dp[to][child] for all children of "to".`↵
`Then dp[from][to] = 1 if and only if dp[to][child]==1 for all children of "to" and the color[child]==color[to] for all children of "to".`↵
`Otherwise, dp[from][to]=0;`↵
↵
↵
Now, to compute the final answer, Let's iterate over all "from" nodes, and for each "to" such that "to" is adjacent to "from", if dp[from][to]==1, then final answer="YES", and node="from".↵
↵
If no such "from" is found then answer="NO";↵
↵
↵
↵
↵
`But this looks like O(n^2) solution. But, if we observe carefully, we see that each "from","to" pair of nodes corresponds to a directed edge going from node "from" to node "to". Since there are exactly n-1 edges, the no. of "from","to" pairs = 2*(n-1).`↵
↵
↵
↵
↵
Here is my submission ----> [http://mirror.codeforces.com/contest/764/submission/24382711](http://mirror.codeforces.com/contest/764/submission/24382711). ↵
↵
~~~~~↵
NOTE: In this solution instead of passing -> "from","to" to dfs function, I have passed "from","index of 'to' in adj[from]". I have made multiple dfs calls but each call is computed exactly once, since I have made a vis[] array which keeps track of it.↵
~~~~~↵
NOTE: If we put a break statement in dfs for loop, we get AC. Lol :P [Here](http://mirror.codeforces.com/contest/764/submission/24384370) is the AC submission. I don't know why it does not get TLE, as the time complexity remains the same, but it is slightly optimized.↵
↵
Please tell where I am wrong in calculating the time complexity?↵
Thanks in advance.↵
↵
My approach is as follows:↵
↵
`Let dp[from][to] = 1 if all nodes in the subtree of "to" (including "to") are of the same color when we perform dfs from node "from" and "to" is the child of node "from".`↵
`dp[from][to] = 0, otherwise.`↵
↵
↵
↵
↵
`To calculate dp[from][to] we use dfs. Let node "to" have k children, then let's compute dp[to][child] for all children of "to".`↵
`Then dp[from][to] = 1 if and only if dp[to][child]==1 for all children of "to" and the color[child]==color[to] for all children of "to".`↵
`Otherwise, dp[from][to]=0;`↵
↵
↵
Now, to compute the final answer, Let's iterate over all "from" nodes, and for each "to" such that "to" is adjacent to "from", if dp[from][to]==1, then final answer="YES", and node="from".↵
↵
If no such "from" is found then answer="NO";↵
↵
↵
↵
↵
`But this looks like O(n^2) solution. But, if we observe carefully, we see that each "from","to" pair of nodes corresponds to a directed edge going from node "from" to node "to". Since there are exactly n-1 edges, the no. of "from","to" pairs = 2*(n-1).`↵
↵
↵
↵
↵
Here is my submission ----> [http://mirror.codeforces.com/contest/764/submission/24382711](http://mirror.codeforces.com/contest/764/submission/24382711). ↵
↵
~~~~~↵
NOTE: In this solution instead of passing -> "from","to" to dfs function, I have passed "from","index of 'to' in adj[from]". I have made multiple dfs calls but each call is computed exactly once, since I have made a vis[] array which keeps track of it.↵
~~~~~↵
NOTE: If we put a break statement in dfs for loop, we get AC. Lol :P [Here](http://mirror.codeforces.com/contest/764/submission/24384370) is the AC submission. I don't know why it does not get TLE, as the time complexity remains the same, but it is slightly optimized.↵
↵
Please tell where I am wrong in calculating the time complexity?↵
Thanks in advance.↵
↵
