Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int n, ans[100100], timeIn[100100], timeOut[100100], par[100100], step; 
int p[100100][20], depth[100100];
vector <int> a[100100];

void visit(int x)
{
    timeIn[x] = ++step;
    for (int i = 0; i < int(a[x].size()); i++)
    {
        int y = a[x][i];
        if (y != par[x]) 
        {
            p[y][0] = par[y] = x; 
            depth[y] = depth[x] + 1;
            visit(y);
        }
    }
    timeOut[x] = step;
}

bool cmp(int u, int v)
{
    return timeIn[u] < timeIn[v];
}

void preLCA()
{
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            p[j][i] = p[p[j][i - 1]][i - 1];
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (depth[x] - (1 << i) >= depth[y])
            x = p[x][i];
    if (x == y) return x;

    for (int i = 19; i >= 0; i--)
        if (p[x][i] != p[y][i])
            x = p[x][i], y = p[y][i];
    return p[x][0];
}

int main()
{
    int x, y;

    cin >> n;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }

    visit(1);
    preLCA();

    for (int i = 1; i <= n; i++)
    {
        vector <int> b;
        for (int j = i; j <= n; j += i) b.push_back(j);
        sort(b.begin(), b.end(), cmp);

        long long ans = depth[b[0]];
        for (int i = 1; i < int(b.size()); i++)
            ans += depth[b[i]] - depth[lca(b[i], b[i - 1])];

        printf("%lld\n", ans * 2);
    }
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;
VI a[N];
int par[N][20], dis[N], d[N];
int n, timer, lg;

void dfs(int u) {
    dis[u] = ++timer;
    TR(v, a[u]) if (*v != par[u][0]) {
        d[*v] = d[u] + 1;
        par[*v][0] = u;
        dfs(*v);
    }
}

bool cmp(const int &a, const int &b)
    {return dis[a] < dis[b];}

int lca(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    REPD(i, lg, 0)
        if (d[v] - d[u] >= (1 << i)) v = par[v][i];
    if (u == v) return u;
    REPD(i, lg, 0) if (par[u][i] != par[v][i]) {
        u = par[u][i]; v = par[v][i];
    }
    return par[u][0];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int u, v;
    FOR(i, 1, n) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
    }
    dfs(1);
    lg = log2(n) + 1;
    REP(j, 1, lg) REP(i, 1, n)
    par[i][j] = par[par[i][j - 1]][j - 1];

    REP(i, 1, n) {
        VI node (1, 1);
        for(int j = i; j <= n; j += i)
            node.PB(j);
        sort(ALL(node), cmp);
        int ans = d[node[SZ(node) - 1]];
        FOR(j, 1, SZ(node)) {
            int p = lca(node[j - 1], node[j]);
            ans += d[node[j - 1]] + d[node[j]] - d[p] - d[p];
        }
        cout << ans << '\n';
    }
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 100111;

int n, h[MN], father[22][MN], getOut[MN], num;
bool leaf[MN];
vector<int> ke[MN];

void dfs(int u, int fu) {
    leaf[u] = true;
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == fu) continue;

        leaf[u] = false;

        h[v] = h[u] + 1;
        father[0][v] = u;
        dfs(v, u);
    }
    getOut[u] = ++num;
}

void init() {
    FOR(i,1,18)
    FOR(u,1,n) {
        father[i][u] = father[i-1][father[i-1][u]];
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    if (h[u] > h[v]) {
        FORD(i,18,0) {
            int x = father[i][u];
            if (!x) continue;

            if (h[x] >= h[v]) u = x;
        }
    }
    if (u == v) return u;

    FORD(i,18,0)
    if (father[i][u] != father[i][v]) {
        u = father[i][u];
        v = father[i][v];
    }
    return father[0][u];
}

int top, x[MN];

bool cmp(int u, int v) {
    return getOut[u] < getOut[v];
}

int main() {
    scanf("%d", &n);
    FOR(i,2,n) {
        int u, v; scanf("%d%d", &u, &v);
        ke[u].PB(v); ke[v].PB(u);
    }
    dfs(1, -1);
    init();

    // PR(h, n);

    FOR(i,1,n) {
        // DEBUG(i);
        top = 0;
        for(int j = i; j <= n; j += i)
            x[++top] = j;

        sort(x+1, x+top+1, cmp);

        ll res = h[x[1]];
        int last = x[1];
        FOR(j,2,top) {
            int cur = lca(last, x[j]);
            // last --> x[j]
            res += h[last] + h[x[j]] - h[cur] - h[cur];

            last = x[j];
        }
        res += h[last];
        printf("%lld\n", res);
    }
    return 0;
}