--- a/dom/animation/test/mozilla/file_restyles.html
+++ b/dom/animation/test/mozilla/file_restyles.html
@@ -1275,32 +1275,16 @@ waitForAllPaints(() => {
     div.remove();
 
     var markers = await observeStyling(5);
     is(markers.length, 0,
        'Animation on orphaned element should not cause restyles');
 
     document.body.appendChild(div);
 
-    markers = await observeStyling(1);
-    if (isServo) {
-      // In Servo, we explicitly set important_rules_change flag to the element
-      // in compute_style() during the initial normal traversal right after
-      // re-attaching which leads to invoking a SequentialTask for
-      // CascadeResults which ends up calling RequestRestyle(Standard). As a
-      // result, the animation is restyled during a second animation restyle in
-      // the first frame.
-      todo_is(markers.length, 1,
-              'Bug 1388560 We should observe one restyle in the first frame ' +
-              'right after re-attaching to the document');
-    } else {
-      is(markers.length, 1,
-         'We should observe one restyle in the first frame right after ' +
-         're-attaching to the document');
-    }
     markers = await observeStyling(5);
     is(markers.length, 5,
        'Animation on re-attached to the document begins to update style');
 
     await ensureElementRemoval(div);
   });
 
   add_task_if_omta_enabled(

--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -666,24 +666,33 @@ Gecko_UpdateAnimations(RawGeckoElementBo
   }
 
   if (aTasks & UpdateAnimationsTasks::EffectProperties) {
     presContext->EffectCompositor()->UpdateEffectProperties(
       aComputedData, const_cast<dom::Element*>(aElement), pseudoType);
   }
 
   if (aTasks & UpdateAnimationsTasks::CascadeResults) {
-    // This task will be scheduled if we detected any changes to !important
-    // rules. We post a restyle here so that we can update the cascade
-    // results in the pre-traversal of the next restyle.
-    presContext->EffectCompositor()
-               ->RequestRestyle(const_cast<Element*>(aElement),
-                                pseudoType,
-                                EffectCompositor::RestyleType::Standard,
-                                EffectCompositor::CascadeLevel::Animations);
+    EffectSet* effectSet = EffectSet::GetEffectSet(aElement, pseudoType);
+    // CSS animations/transitions might have been destroyed as part of the above
+    // steps so before updating cascade results, we check if there are still any
+    // animations to update.
+    if (effectSet) {
+      // We call UpdateCascadeResults directly (intead of
+      // MaybeUpdateCascadeResults) since we know for sure that the cascade has
+      // changed, but we were unable to call MarkCascadeUpdated when we noticed
+      // it since we avoid mutating state as part of the Servo parallel
+      // traversal.
+      presContext->EffectCompositor()
+                 ->UpdateCascadeResults(StyleBackendType::Servo,
+                                        *effectSet,
+                                        const_cast<Element*>(aElement),
+                                        pseudoType,
+                                        nullptr);
+    }
   }
 
   if (aTasks & UpdateAnimationsTasks::DisplayChangedFromNone) {
     presContext->EffectCompositor()
                ->RequestRestyle(const_cast<Element*>(aElement),
                                 pseudoType,
                                 EffectCompositor::RestyleType::Standard,
                                 EffectCompositor::CascadeLevel::Animations);