The holographic entanglement entropy for the most general higher derivativegravity is investigated. We find a new type of Wald entropy, which appears onentangling surface without the rotational symmetry and reduces to usual Waldentropy on Killing horizon. Furthermore, we obtain a formal formula of HEE forthe most general higher derivative gravity and work it out exactly for somesquashed cones. As an important application, we derive HEE for gravitationalaction with one derivative of the curvature when the extrinsic curvaturevanishes. We also study some toy models with non-zero extrinsic curvature. Weprove that our formula yields the correct universal term of entanglemententropy for 4d CFTs. Furthermore, we solve the puzzle raised by Hung, Myers andSmolkin that the logarithmic term of entanglement entropy derived from Weylanomaly of CFTs does not match the holographic result even if the extrinsiccurvature vanishes. We find that such mismatch comes from the `anomaly ofentropy' of the derivative of curvature. After considering such contributionscarefully, we resolve the puzzle successfully. In general, we need to fix thesplitting problem for the conical metrics in order to derive the holographicentanglement entropy. We find that, at least for Einstein gravity, thesplitting problem can be fixed by using equations of motion. How to derive thesplittings for higher derivative gravity is a non-trivial and open question.For simplicity, we ignore the splitting problem in this paper and find that itdoes not affect our main results.