题解：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)，可以通过此题。

代码：

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