P11624 挂掉的模版 题解

Pig_Eat_Earth · 2025-01-28 23:58:57 · 题解

P11624 挂掉的模版 题解

原题传送门

记号约定

• ## 小观察 以下讨论 $FakeLCA_{u,v}$ 的情况。显然，u 和 v 的跳转次数相同。 1. $dep_u=dep_v \because dep_{lca_{u,v}}-dep_u=dep_{lca_{u,v}}-dep_v \therefore FakeLCA_{u,v}=lca_{u,v}
  1. dep_u\neq dep_v

     一个节点到达根节点后，会停留在根节点。 图为样例 3，以 u=5,v=9 为例，图中圆框为 u 跳转得，方框为 v 跳转得，同种颜色为跳转同样次数。可见，当 u 和 v 深度不同时，只有根节点处跳转次数相同，所以 FakeLCA_{u,v}=root。

于是，我们可以得出结论，FakeLCA_{u,v}=lca_{u,v} 当且仅当满足以下两种情况：

2. lca_{u,v}=root

其中第二种情况可以分为：

1. u 与 v 分属根节点不同子节点的子树（b）
2. ## 解法 答案即为满足（a）（b）（c）中至少一条的有序节点对数。 但是注意到，（a）与（b）可能重叠。因此，采用以下策略：
3. 满足（c）的总共 2n-1 对，即 \forall 1\le i\le n，有 (1,i) 和 (i,1) 两对，并减去重复计算的 (1,1)。
4. DFS 一遍，统计出满足（b）的对数。注意到，有序对数即为无序对数的 2 倍。（本条中“答案”指有序对数）
   对于一个要并入答案的子树 i，增加了： \sum^{i-1}_{j=1}(sz_i\cdot sz_j)=sz_i\cdot\sum^{i-1}_{j=1}sz_j

   注意到，\sum sz_j 可以在计算答案后维护，则计算上式的值为 O(1) 的。

5. 统计出满足（a）而不满足（b）的无序对数，即在以根节点的各个子节点为根的子树内统计出 l，并将答案增加 \sum l_d^2。

   时间复杂度

   除根节点外，每个节点都被 DFS 了两遍，而节点深度不会超过 n，故为 O(n)。

   Code

   
   #include <bits/stdc++.h>
   #define UP(i, l, r) for(register int (i) = (l); (i) <= (r); ++ (i))
   #define DN(i, l, r) for(register int (i) = (r); (i) >= (l); -- (i))
   #define EUP(t, i, l, r, d) for(register (t) (i) = (l); (i) <= (r); (i) += (d))
   #define EDN(t, i, l, r, d) for(register (t) (i) = (r); (i) >= (l); (i) -= (d))
   #define INF 0x3f3f3f3f
   #define INFLL 0x3f3f3f3f3f3f3f3f
   #define INFB 0x3f
   using namespace std;
   using ll = long long;
   const int N = 1e6;
   int n, fa[N + 5], sz[N + 5], md, rt;
   vector<int> g[N + 5];
   ll ans, l[N + 5], ss;

void dfs1(int u){ sz[u] = 1; for(register int v : g[u]){ dfs1(v); sz[u] += sz[v]; } if(fa[u] == rt && u != rt){ ans += ss * sz[u]; ss += sz[u]; } }

void dfs2(int u, int d){ md = max(md, d); ++ l[d]; for(register int v : g[u]) dfs2(v, d + 1); }

int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; if(n == 1){ cout << 1; return 0; } UP(i, 1, n){ cin >> fa[i]; if(fa[i] == i) rt = i; else g[fa[i]].push_back(i); } ans += (n << 1) - 1; // c dfs1(rt); // b ans <<= 1; // 无序转有序 for(register int r : g[rt]){ // a & !b UP(i, 1, md) l[i] = 0; md = 0; dfs2(r, 1); UP(i, 1, md) ans += l[i] * l[i]; } cout << ans; return 0; }