hdu2586 How far away ？

题目链接

题目大意

??询问树上两点距离

解题思路

??树剖求lca，\(dis(a,b) = dis(rt, a)+dis(rt, b)-dis(rt, lca(a, b))\times 2\)。

代码

const int maxn = 1e5+10;
struct E {
    int to, w, nxt;
} e[maxn<<2];
int h[maxn], tot;
void add(int u, int v, int w) {
    e[++tot] = {v, w, h[u]};
    h[u] = tot;
}
int dep[maxn], fa[maxn], sz[maxn], son[maxn], dis[maxn];
void dfs1(int u, int p) {
    sz[u] = 1;
    for (int i = h[u]; i; i=e[i].nxt) {
        int v = e[i].to;
        if (v==p) continue;
        dep[v] = dep[u]+1;
        dis[v] = dis[u]+e[i].w;
        fa[v] = u;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v]>sz[son[u]]) son[u] = v;
    }
}
int top[maxn];
void dfs2(int u) {
    if (u==son[fa[u]]) top[u] = top[fa[u]];
    else top[u] = u;
    for (int i = h[u]; i; i=e[i].nxt) {
        int v = e[i].to;
        if (v!=fa[u]) dfs2(v);
    }
}
int lca(int u, int v) {
    while(top[u]!=top[v]) {
        if (dep[top[u]]>dep[top[v]]) u = fa[top[u]];
        else v = fa[top[v]];
    }
    return dep[u]>dep[v]?v:u;
}
int n, m;
void init() {
    tot = 0;
    for (int i = 0; i<=n; ++i) h[i] = 0, son[i] = 0;
}
int main(void) {
    int __; cin >> __;
    while(__--) {
        cin >> n >> m; 
        init();
        for (int i = 1, a, b, c; i<n; ++i) {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }
        dfs1(1, 0);
        dfs2(1);
        while(m--) {
            int a, b; scanf("%d%d", &a, &b);
            printf("%d\n", dis[a]+dis[b]-dis[lca(a, b)]*2);
        }
    }   
    return 0;
}   

树链剖分入门

原文：https://www.cnblogs.com/shuitiangong/p/14761758.html