P16161 [ICPC 2016 NAIPC] Tourists

ooliver 发布于 8 小时前 31 次阅读 OI

AI 摘要

边枚举所有点对O(n log² n)？巧妙变换后只需考察所有倍数关系点对，复杂度直降O(n log n)！树剖求LCA，代码简洁高效——这篇博客教你如何用数学优化暴力枚举。

P16161 [ICPC 2016 NAIPC] Tourists

不难看出，枚举所有的点对的复杂度应为：

$$
\begin{aligned}
&\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\dots+1 \\
=&n(1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}) \\
\approx&n\ln n
\end{aligned}
$$

这时，对于每组点对我们树剖求 LCA，时间复杂度为 $O(\log n)$，所以总复杂度为 $O(n\log^2 n)$，可以通过此题。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+5; 
int n,ans;
int fa[N],top[N],son[N],siz[N],dep[N];
vector<int> t[N];

void dfs1(int u,int f){
	fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
	for(int v:t[u]){
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}

void dfs2(int u,int topf){
	top[u]=topf;
	if(!son[u]) return;
	dfs2(son[u],topf);
	for(int v:t[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}

int lca(int a,int b){
	while(top[a]!=top[b]){
		if(dep[top[a]]>dep[top[b]]) a=fa[top[a]];
		else b=fa[top[b]];
	}
	return (dep[a]>dep[b]?b:a);
}

signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		t[u].push_back(v);
		t[v].push_back(u);
	} 
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=n;i++) for(int j=2;i*j<=n;j++) ans+=dep[i]+dep[i*j]-2*dep[lca(i,i*j)]+1;
    cout<<ans;
	return 0;
}