P11624 挂掉的模版题解

记号约定

$FakeLCA_{u,v}$ 、 $fa_i$ ：如原题所述。
$lca_{u,v}$ ：u 与 v 的最近公共祖先
$root$ ：根节点
$dep_u$ ：节点 u 的深度
$sz_u$ ：以 u 为根的子树的大小（节点数）
$l_d$ ：在统计范围内深度等于 d 的节点数

小观察

以下讨论

FakeLCA_{u,v}

的情况。显然，u 和 v 的跳转次数相同。

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

于是，我们可以得出结论，

FakeLCA_{u,v}=lca_{u,v}

当且仅当满足以下两种情况：

$dep_u=dep_v$ （a）
$lca_{u,v}=root$

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

u 与 v 分属根节点不同子节点的子树（b）
$u=root$ 或 $v=root$ （c）

解法

答案即为满足（a）（b）（c）中至少一条的有序节点对数。
但是注意到，（a）与（b）可能重叠。因此，采用以下策略：

满足（c）的总共 $2n-1$ 对，即 $\forall 1\le i\le n$ ，有 $(1,i)$ 和 $(i,1)$ 两对，并减去重复计算的 $(1,1)$ 。
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)$ 的。
统计出满足（a）而不满足（b）的无序对数，即在以根节点的各个子节点为根的子树内统计出 $l$ ，并将答案增加 $\sum l_d^2$ 。

时间复杂度

除根节点外，每个节点都被 DFS 了两遍，而节点深度不会超过

n

，故为

O(n)

。

Code

CPP

#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;
}

P11624 挂掉的模版题解

文章操作

P11624 挂掉的模版题解

记号约定

小观察

解法

时间复杂度

Code

相关推荐

评论

P11624 挂掉的模版题解

文章操作

P11624 挂掉的模版 题解

记号约定

小观察

解法

时间复杂度

Code

相关推荐

评论

P11624 挂掉的模版题解