P16161 [ICPC 2016 NAIPC] Tourists · ooliver

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 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 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>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs1(1,0); dfs2(1,1); for(int i=1;i `#include 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 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;in;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;in;i++) for(int j=2;i*jn;j++) ans+=dep[i]+dep[i*j]-2*dep[lca(i,i*j)]+1; coutans; return 0; }`