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>
#include <queue>
#include <cmath>
#define N 10010
using namespace std;

int n,c,re,step,dist[111][N],isSpecial[N],h[N],specialNum;
int dis[N],fin[N],hMin[16][N*3];
vector <int> a[N],colorList[N];
queue <int> q;

void read()
{
    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);
    }
    cin >> c;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        colorList[x].push_back(i);
    }
}

void BFS(int x,int z)
{
    while (!q.empty()) q.pop();
    for (int i=0;i<int(colorList[x].size());i++)
    {
        int y=colorList[x][i];
        q.push(y);
        dist[z][y]=1;
    }
    while (!q.empty())
    {
        int y=q.front(); q.pop();
        for (int i=0;i<int(a[y].size());i++)
        {
            int t=a[y][i];
            if (!dist[z][t]) 
            {
                dist[z][t]=dist[z][y]+1;
                q.push(t);
            }
        }
    }
}

void special()
{
    for (int i=1;i<=c;i++)
        if (int(colorList[i].size())>100)
        {
            isSpecial[i]=++specialNum;
            BFS(i,specialNum);
        }
}

void visit(int x,int Par)
{
    hMin[0][++step]=h[x]; dis[x]=step;
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i];
        if (y==Par) continue;
        hMin[0][++step]=h[x];
        h[y]=h[x]+1;
        visit(y,x);
    }
    fin[x]=step;
}

void preRMQ()
{
    for (int i=1;i<=15;i++)
        for (int j=1;j<=step;j++)
        {
            int k=j+(1<<(i-1));
            if (k<=step && hMin[i-1][k]<hMin[i-1][j]) hMin[i][j]=hMin[i-1][k];
            else hMin[i][j]=hMin[i-1][j];
        }
}

int RMQ(int x,int y)
{
    int l=min(dis[x],dis[y]), r=max(fin[x],fin[y]);
    int lg=int(log(r-l+1)/log(2));
    return min(hMin[lg][l],hMin[lg][r-(1<<lg)+1]);
}

int main()
{
    read();
    special();
    visit(1,0);
    preRMQ();
    int m;
    cin >> m;
    while (m--)
    {
        int x,color;
        scanf("%d%d",&x,&color);
        if (isSpecial[color]) printf("%d\n",dist[isSpecial[color]][x]-1);
        else
        {
            int re=n+1;
            for (int i=0;i<int(colorList[color].size());i++)
            {
                int y=colorList[color][i];
                re=min(re,h[x]+h[y]-2*RMQ(x,y));
            }
            printf("%d\n",re);
        }
    }
    return 0;
}

Code mẫu của happyboy99x

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

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 10000, LOGN = 13, INF = 1e9;
vector<int> e;
int l[2*N], h[N], c[N], num[N], n, rmq[2*N][LOGN+2], id[N], lg[2*N], nc;
vector<int> g[N], d[N];

void enter() {
    cin >> n;
    for(int i = 0; i < n-1; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> nc;
    for(int i = 0; i < n; ++i)
        cin >> c[i], ++num[--c[i]];
}

void bfs(int color, vector<int> &d) {
    if(num[color] * num[color] < n) return;
    d.assign(n, INF);
    queue<int> q;
    for(int u = 0; u < n; ++u) if(c[u] == color)
        q.push(u), d[u] = 0;
    for(int step = 0; !q.empty(); ++step)
        for(int Z = q.size(); Z > 0; --Z) {
            int u = q.front(); q.pop();
            TR(g[u], v) if(d[*v] == INF)
                d[*v] = d[u] + 1, q.push(*v);
        }
}

void dfs(int u = 0, int lvl = 0, int p = -1) {
    h[u] = e.size();
    TR(g[u], v) if(*v != p)
        l[e.size()] = lvl, e.push_back(u), dfs(*v, lvl+1, u);
    l[e.size()] = lvl; e.push_back(u);
}

void initRMQ(int n) {
    for(int i = 1; i <= n; ++i) {
        for(lg[i] = 0; 1 << lg[i] <= i; ++lg[i]); --lg[i];
    }
    memset(rmq, -1, sizeof rmq);
    for(int i = 0; i < n; ++i) rmq[i][0] = i;
    for(int j = 1; 1 << j <= n; ++j)
        for(int i = 0; i + (1 << j) - 1 < n; ++i)
            rmq[i][j] = l[rmq[i][j-1]] < l[rmq[i+(1<<(j-1))][j-1]] ? rmq[i][j-1] : rmq[i+(1<<(j-1))][j-1];
}

int getRMQ(int u, int v) {
    int k = lg[v-u+1];
    return l[rmq[u][k]] < l[rmq[v-(1<<k)+1][k]] ? rmq[u][k] : rmq[v-(1<<k)+1][k];
}

int getLCA(int u, int v) {
    if(h[u] > h[v]) return getLCA(v, u);
    return e[getRMQ(h[u], h[v])];
}

void solve() {
    int q; cin >> q;
    while(q-- > 0) {
        int u, col; cin >> u >> col; --u; --col;
        if(num[col] * num[col] >= n) cout << d[col][u] << '\n';
        else {
            int res = INF;
            for(int v = 0; v < n; ++v) if(c[v] == col)
                res = min(res, l[h[v]] + l[h[u]] - 2 * l[h[getLCA(u, v)]]);
            cout << res << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    for(int x = 0; x < nc; ++x) bfs(x, d[x]);
    dfs();
    initRMQ(e.size());
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 10004;
const int lim = 25;
const int oo = trunc(1e9) + 9;
using namespace std;
struct arr{
    int a[N];
};

vector<arr> d;
vector<int> a[N], bar[N];
bool visit[N], memo[N];
int h[N], Pow[20], Q[N], coc[N], pos[N];
int par[N][20];
int n, m, c, lg, res, cnt;

void DFS(int u) {
    visit[u] = true;
    int v;
    for(int i=0; i<a[u].size(); i++) {
        v = a[u][i];
        if (!visit[v]) {
            h[v] = h[u] + 1;
            par[v][0] = u;
            DFS(v);
        }
    }
}

void initLCA() {
    lg = trunc(log2(n) + 1);
    Pow[0] = 1;
    int i, j;
    for(i=1; i<=lg; i++) Pow[i] = Pow[i-1] + Pow[i-1];
    for(j=1; j<=lg; j++)
    for(i=1; i<=n; i++)
        par[i][j] = par[par[i][j-1]][j-1];
}

void Jump(int& x, int y) {
    for(int i = lg; i>=0; i--) {
        if (Pow[i] <= y) {
            x = par[x][i];
            y -= Pow[i];
        }
    }
}

int LCA(int u, int v) {
    if (h[u] > h[v]) Jump(u, h[u] - h[v]); else Jump(v, h[v] - h[u]);
    if (u == v) return u;
    for(int i=lg; i>=0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

void BFS(int color) {
    arr aa;
    d.push_back(aa);
    int i, u, v;
    for(i=1; i<=n; i++) visit[i] = false;
    int l = 1, r = 0;
    for(i=0; i<bar[color].size(); i++) {
        v = bar[color][i];
        Q[++r] = v; d[pos[color]].a[v] = 0;
        visit[v] = true;
    }
    while (l <= r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i];
            if (!visit[v]) {
                Q[++r] = v;
                visit[v] = true;
                d[pos[color]].a[v] = d[pos[color]].a[u] + 1;
            }
        }
    }
}

int main()
{
    //freopen("KTREEC.in", "r", stdin);
    scanf("%d\n", &n);
    int i, j, u, v, cc, p;
    for(i=1; i<n; i++) {
        scanf("%d %d\n", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    scanf("%d\n", &c);
    for(i=1; i<=n; i++) {
        scanf("%d", &coc[i]);
        bar[coc[i]].push_back(i);
    }
    h[1] = 1; DFS(1);
    initLCA();
    for(i=1; i<=c; i++) {
        if (bar[i].size() >= lim) {
            pos[i] = cnt++;
            memo[i] = true;
            BFS(i);
        }
    }
    scanf("%d\n", &m);
    for(i=1; i<=m; i++) {
        scanf("%d %d\n", &u, &cc);
        if (memo[cc]) printf("%d\n", d[pos[cc]].a[u]);
        else {
            res = oo;
            for(j=0; j<bar[cc].size(); j++) {
                v = bar[cc][j];
                p = LCA(u, v);
                res = min(res, h[u] + h[v] - h[p] - h[p]);
            }
            printf("%d\n", res);
        }
    }
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <vector>

#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)
using namespace std;

const int MN = 10111;
const int GH = 25;

int cnt[MN], h[MN], d[422][MN], qu[MN], father[16][MN], id[MN];
vector<int> ls[MN], ke[MN];
int n, c, color[MN];

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

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

void bfs(int cc, int id) {
    int first = 1, last = 0;
    FOR(i,1,n) if (color[i] == cc) {
        ++last; qu[last] = i;
        d[id][i] = 0;
    }
    else d[id][i] = -1;

    while (first <= last) {
        int u = qu[first++];
        REP(i,ke[u].size()) {
            int v = ke[u][i];
            if (d[id][v] < 0) {
                qu[++last] = v;
                d[id][v] = d[id][u] + 1;
            }
        }
    }
}

void init() {
    h[1] = 1;
    dfs(1, -1);
    FOR(i,1,14)
    FOR(u,1,n)
        father[i][u] = father[i-1][father[i-1][u]];

    int nId = 0;
    FOR(i,1,c) {
        if (cnt[i] >= GH) {
            id[i] = ++nId;
            bfs(i, id[i]);
        }
    }
    FOR(i,1,n)
        if (cnt[color[i]] < GH)
            ls[color[i]].push_back(i);
}

int len(int u, int v) {
    int res = 0;
    if (h[u] != h[v]) {
        if (h[u] < h[v]) swap(u, v);

        FORD(i,14,0)
        if (h[father[i][u]] >= h[v]) {
            u = father[i][u];
            res += 1<<i;
        }
    }
    if (u == v) return res;

    FORD(i,14,0) if (father[i][u] != father[i][v]) {
        u = father[i][u]; v = father[i][v];
        res += 1 << (i+1);
    }
    return res + 2;
}

int main() {
    scanf("%d", &n);
    FOR(i,2,n) {
        int u, v; scanf("%d%d", &u, &v);
        ke[u].push_back(v); ke[v].push_back(u);
    }
    scanf("%d", &c);
    FOR(i,1,n) {
        scanf("%d", &color[i]);
        ++cnt[color[i]];
    }

    init();

    // FOR(i,1,c) {
    //     if (cnt[i] >= GH) {
    //         cout << "Good color " << i << endl;
    //         FOR(u,1,n) cout << d[id[i]][u] << ' '; cout << endl;
    //     }
    //     else {
    //         cout << "Bad color " << i << endl;
    //         REP(u,ls[i].size()) cout << ls[i][u] << ' '; cout << endl;
    //     }
    // }

    int q; scanf("%d", &q);
    while (q--) {
        int u, cc; scanf("%d%d", &u, &cc);

        if (cnt[cc] >= GH) {
            printf("%d\n", d[id[cc]][u]);
        }
        else {
            int res = 1000111;
            REP(i,ls[cc].size()) {
                res = min(res, len(ls[cc][i], u));
            }
            printf("%d\n", res);
        }
    }
    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   30303
using namespace std;
queue<int> q;
vector<int> g[MAX];
vector<int> col[MAX];
vector<int> dst[MAX];
vector<int> euler;
int h[MAX];
int dis[MAX];
int fin[MAX];
bool vst[MAX];
int rmq[MAX][15];
int lg2[MAX];
int m,n,p,lim;
int min(const int &x,const int &y) {
    if (x<y) return (x); else return (y);
}
int max(const int &x,const int &y) {
    if (x>y) return (x); else return (y);
}
int mh(const int &x,const int &y) {
    if (h[x]<h[y]) return (x); else return (y);
}
void loadtree(void) {
    scanf("%d",&n);
    int i,u,v;
    for (i=1;i<n;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    scanf("%d",&m);
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&u);
        col[u].push_back(i);
        dis[i]=-1;
    }
}
void visit(const int &u) {
    int i,v;
    for (i=0;i<g[u].size();i=i+1) {
        v=g[u][i];
        if (!vst[v]) {
            vst[v]=true;
            h[v]=h[u]+1;
            euler.push_back(u);
            visit(v);
            euler.push_back(u);
        }
    }
    euler.push_back(u);
}
void setup_lca(void) {
    int i,j;
    for (i=0;i<euler.size();i=i+1) {
        if (dis[euler[i]]<0) dis[euler[i]]=i;
        fin[euler[i]]=i;
    }
    for (i=1;i<=euler.size();i=i+1) {
        lg2[i]=0;
        while ((1<<lg2[i])<=i) lg2[i]++;
        lg2[i]--;
    }
    for (i=0;i<euler.size();i=i+1) rmq[i][0]=euler[i];
    for (j=1;j<15;j=j+1)
        for (i=0;i+(1<<j)-1<euler.size();i=i+1) 
            rmq[i][j]=mh(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
}
int minval(const int &i,const int &j) {
    int k=lg2[j-i+1];
    return (mh(rmq[i][k],rmq[j-(1<<k)+1][k]));
}
int lca(const int &u,const int &v) {
    int i=min(dis[u],dis[v]);
    int j=max(fin[u],fin[v]);
    return (minval(i,j));
}
int distan(const int &u,const int &v) {
    int w=lca(u,v);
    return (h[u]+h[v]-2*h[w]);
}
void BFS(const int &y) {    
    while (!q.empty()) q.pop();
    int i,x,v;  
    for (i=1;i<=n;i=i+1) {      
        vst[i]=false;
        dst[y].push_back(0);
    }       
    for (i=0;i<col[y].size();i=i+1) {       
        v=col[y][i];                
        vst[v]=true;
        q.push(v);
    }   
    while (!q.empty()) {
        x=q.front();q.pop();
        for (i=0;i<g[x].size();i=i+1) {
            v=g[x][i];
            if (!vst[v]) {
                vst[v]=true;
                dst[y][v-1]=dst[y][x-1]+1;
                q.push(v);
            }
        }
    }
}
void pre_answer(void) {
    vst[1]=true;
    h[1]=0;
    visit(1);
    setup_lca();
    int i;
    lim=0;
    while (lim*lim<n) lim++;
    for (i=1;i<=m;i=i+1)
        if (col[i].size()>=lim) BFS(i);
}
int result(const int &u,const int &y) {
    if (col[y].size()>=lim) return (dst[y][u-1]);
    int i;
    int res=MAX+1;
    for (i=0;i<col[y].size();i=i+1)
        res=min(res,distan(u,col[y][i]));
    return (res);
}
void answer(void) {
    scanf("%d",&p);
    int i,u,y;
    for (i=1;i<=p;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&y);
        printf("%d\n",result(u,y));
    }   
}
int main(void) {
    //freopen("tmp.txt","r",stdin); 
    loadtree();
    pre_answer();   
    answer();
    return 0;
}