101002I.md

I. Tourists

Link

Solution

lca裸题，将i（从1到n）和i*k（从1到n）之间的距离累加起来即可，注意节点范围是2e5但答案的范围是long long。

Code

int n;
vector<int>G[maxn];
int fa[maxn][31], dep[maxn], lg2[maxn];

void dfs(int rt, int f) {
    fa[rt][0] = f;
    dep[rt] = dep[f] + 1;
    for (int i = 1; i < 31; i++)fa[rt][i] = fa[fa[rt][i - 1]][i - 1];
    int sz = G[rt].size();
    for (int i = 0; i < sz; i++)if (G[rt][i] != f)dfs(G[rt][i], rt);
}

void init() {
    for (int i = 1; i <= n; i++)lg2[i] = lg2[i - 1] + (1 << lg2[i - 1] == i);
}

int lca(int x, int y) {
    if (dep[x] < dep[y])swap(x, y);
    while (dep[x] > dep[y])x = fa[x][lg2[dep[x] - dep[y]] - 1];
    if (x == y)return x;
    for (int i = lg2[dep[x]] - 1; i >= 0; i--)
        if (fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int main() {
    int x, y;
    LL ans = 0;
    cin >> n;
    init();
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = i * 2; j <= n; j += i)ans += dep[i] + dep[j] - 2 * dep[lca(i, j)] + 1;
    cout << ans << endl;
    return 0;
}